Maximum sum of non-overlapping subarrays of length atmost K

0 0 8 minutes read

Given an integer array ‘arr’ of length N and an integer ‘k’, select some non-overlapping subarrays such that each sub-array if of length at most ‘k’, no two sub-arrays are adjacent and sum of all the elements of the selected sub-arrays are maximum.
Examples:

Input : arr[] = {-1, 2, -3, 4, 5}, k = 2
Output : 11
Sub-arrays that maximizes sum will be {{2}, {4, 5}}.
Thus, the answer will be 2+4+5 = 11.

Input :arr[] = {1, 1, 1, 1, 1}, k = 1
Output : 3

Naive Approach : A simple way is to generate all possible subsets of elements satisfying above conditions recursively and find the subset with maximum sum.
Time Complexity : O(2^N)
Efficient Approach: A better approach is to use dynamic programming.
Let’s suppose we are at an index ‘i’.
Let dp[i] be defined as the maximum sum of elements of all possible subsets of sub-array {i, n-1} satisfying above conditions.
We will have ‘K+1’ possible choices i.e.

Reject ‘i’ and solve for ‘i+1’.
Select sub-array {i} and solve for ‘i+2’
Select sub-array {i, i+1} and solve for ‘i+3’

Thus, recurrence relation will be:

dp[i] = max(dp[i+1], arr[i]+dp[i+2], arr[i]+arr[i+1]+dp[i+3],
        ...arr[i]+arr[i+1]+arr[i+2]...+arr[i+k-1] + dp[i+k+1])

Below is the implementation of the above approach:

C++

// C++ program to implement above approach
#include <bits/stdc++.h>
#define maxLen 10
using namespace std;
 
// Variable to store states of dp
int dp[maxLen];
 
// Variable to check if a given state has been solved
bool visit[maxLen];
 
// Function to find the maximum sum subsequence
// such that no two elements are adjacent
int maxSum(int arr[], int i, int n, int k)
{
    // Base case
    if (i >= n)
        return 0;
 
    // To check if a state has been solved
    if (visit[i])
        return dp[i];
    visit[i] = 1;
 
    // Variable to store
    // prefix sum for sub-array
    // {i, j}
    int tot = 0;
    dp[i] = maxSum(arr, i + 1, n, k);
 
    // Required recurrence relation
    for (int j = i; j < i + k and j < n; j++) {
        tot += arr[j];
        dp[i] = max(dp[i], tot +
                     maxSum(arr, j + 2, n, k));
    }
 
    // Returning the value
    return dp[i];
}
 
// Driver code
int main()
{
    // Input array
    int arr[] = { -1, 2, -3, 4, 5 };
 
    int k = 2;
 
    int n = sizeof(arr) / sizeof(int);
 
    cout << maxSum(arr, 0, n, k);
 
    return 0;
}

Java

// Java program to implement above approach
import java.io.*;
 
class GFG
{
     
    static int maxLen = 10;
     
    // Variable to store states of dp
    static int dp[] = new int[maxLen];
     
    // Variable to check 
    // if a given state has been solved
    static boolean []visit = new boolean[maxLen];
     
    // Function to find the maximum sum subsequence
    // such that no two elements are adjacent
    static int maxSum(int arr[], int i, 
                    int n, int k)
    {
        // Base case
        if (i >= n)
            return 0;
     
        // To check if a state has been solved
        if (visit[i])
            return dp[i];
        visit[i] = true;
     
        // Variable to store
        // prefix sum for sub-array
        // {i, j}
        int tot = 0;
        dp[i] = maxSum(arr, i + 1, n, k);
     
        // Required recurrence relation
        for (int j = i; j < (i + k) &&
                            (j < n); j++)
        {
            tot += arr[j];
            dp[i] = Math.max(dp[i], tot +
                    maxSum(arr, j + 2, n, k));
        }
     
        // Returning the value
        return dp[i];
    }
 
    // Driver code
    public static void main (String[] args) 
    {
 
        // Input array
        int arr[] = { -1, 2, -3, 4, 5 };
         
        int k = 2;
         
        int n = arr.length;
         
        System.out.println(maxSum(arr, 0, n, k));
    }
}
 
// This code is contributed by ajit.

Python3

# Python3 program to implement above approach 
maxLen = 10
 
# Variable to store states of dp 
dp = [0]*maxLen; 
 
# Variable to check if a given state has been solved 
visit = [0]*maxLen; 
 
# Function to find the maximum sum subsequence 
# such that no two elements are adjacent 
def maxSum(arr, i, n, k) : 
 
    # Base case 
    if (i >= n) :
        return 0; 
 
    # To check if a state has been solved 
    if (visit[i]) : 
        return dp[i]; 
         
    visit[i] = 1; 
 
    # Variable to store 
    # prefix sum for sub-array 
    # {i, j} 
    tot = 0; 
    dp[i] = maxSum(arr, i + 1, n, k); 
 
    # Required recurrence relation 
    j = i
    while (j < i + k and j < n) :
        tot += arr[j]; 
        dp[i] = max(dp[i], tot +
                    maxSum(arr, j + 2, n, k)); 
                     
        j += 1
     
    # Returning the value 
    return dp[i]; 
 
 
# Driver code 
if __name__ == "__main__" : 
 
    # Input array 
    arr = [ -1, 2, -3, 4, 5 ]; 
 
    k = 2; 
 
    n = len(arr); 
 
    print(maxSum(arr, 0, n, k)); 
     
# This code is contributed by AnkitRai01

C#

// C# program to implement above approach
using System;
 
class GFG
{
static int maxLen = 10;
 
// Variable to store states of dp
static int []dp = new int[maxLen];
 
// Variable to check 
// if a given state has been solved
static bool []visit = new bool[maxLen];
 
// Function to find the maximum sum subsequence
// such that no two elements are adjacent
static int maxSum(int []arr, int i, 
                  int n, int k)
{
    // Base case
    if (i >= n)
        return 0;
 
    // To check if a state has been solved
    if (visit[i])
        return dp[i];
    visit[i] = true;
 
    // Variable to store
    // prefix sum for sub-array
    // {i, j}
    int tot = 0;
    dp[i] = maxSum(arr, i + 1, n, k);
 
    // Required recurrence relation
    for (int j = i; j < (i + k) &&
                        (j < n); j++)
    {
        tot += arr[j];
        dp[i] = Math.Max(dp[i], tot +
                  maxSum(arr, j + 2, n, k));
    }
 
    // Returning the value
    return dp[i];
}
 
// Driver code
static public void Main ()
{
 
    // Input array
    int []arr = { -1, 2, -3, 4, 5 };
     
    int k = 2;
     
    int n = arr.Length;
     
    Console.WriteLine (maxSum(arr, 0, n, k));
}
}
 
// This code is contributed by ajit.

Javascript

<script>
    // Javascript program to implement above approach
     
    let maxLen = 10;
   
    // Variable to store states of dp
    let dp = new Array(maxLen);
 
    // Variable to check 
    // if a given state has been solved
    let visit = new Array(maxLen);
 
    // Function to find the maximum sum subsequence
    // such that no two elements are adjacent
    function maxSum(arr, i, n, k)
    {
        // Base case
        if (i >= n)
            return 0;
 
        // To check if a state has been solved
        if (visit[i])
            return dp[i];
        visit[i] = true;
 
        // Variable to store
        // prefix sum for sub-array
        // {i, j}
        let tot = 0;
        dp[i] = maxSum(arr, i + 1, n, k);
 
        // Required recurrence relation
        for (let j = i; j < (i + k) &&
                            (j < n); j++)
        {
            tot += arr[j];
            dp[i] = Math.max(dp[i], tot +
                      maxSum(arr, j + 2, n, k));
        }
 
        // Returning the value
        return dp[i];
    }
     
    // Input array
    let arr = [ -1, 2, -3, 4, 5 ];
       
    let k = 2;
       
    let n = arr.length;
       
    document.write(maxSum(arr, 0, n, k));
 
</script>

Output:

Time Complexity: O(n*k)
Space complexity: O(n)

Efficient approach : Using DP Tabulation method ( Iterative approach )

The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.

Steps to solve this problem :

Create a 1D DP of size n to store the solution of the subproblems.
Initialize the DP with 0.
Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
Create a variable res and to store the final result and update it by iterating through Dp.
Return the final solution stored in res

Implementation :

C++

#include <bits/stdc++.h>
#define maxLen 10
using namespace std;
 
 
// Function to find the maximum sum subsequence
// such that no two elements are adjacent
int maxSum(int arr[], int n, int k)
{
    // DP table
    int dp[n];
     
    // Initializing the DP table
    memset(dp, 0, sizeof(dp));
     
    // Computing the DP table
    for (int i = 0; i < n; i++) {
        int tot = 0;
        for (int j = i - k; j < i; j++) {
            if (j >= 0)
                tot = max(tot, dp[j]);
        }
        dp[i] = tot + arr[i];
    }
     
    // Returning the maximum sum
    int res = 0;
    for (int i = 0; i < n; i++)
        res = max(res, dp[i]);
         
    // return final ans
    return res;
}
 
// Driver code
int main()
{
    // Input array
    int arr[] = { -1, 2, -3, 4, 5 };
     
    int k = 2;
     
    int n = sizeof(arr) / sizeof(int);
     
    cout << maxSum(arr, n, k);
     
    return 0;
}

Java

import java.util.Arrays;
 
class GFG 
{
   
    // Function to find the maximum sum subsequence
    // such that no two elements are adjacent
    static int maxSum(int arr[], int n, int k)
    {
       
        // DP table
        int dp[] = new int[n];
 
        // Initializing the DP table
        Arrays.fill(dp, 0);
 
        // Computing the DP table
        for (int i = 0; i < n; i++) {
            int tot = 0;
            for (int j = i - k; j < i; j++) {
                if (j >= 0)
                    tot = Math.max(tot, dp[j]);
            }
            dp[i] = tot + arr[i];
        }
 
        // Returning the maximum sum
        int res = 0;
        for (int i = 0; i < n; i++)
            res = Math.max(res, dp[i]);
 
        // return final ans
        return res;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Input array
        int arr[] = { -1, 2, -3, 4, 5 };
        int k = 2;
        int n = arr.length;
        System.out.println(maxSum(arr, n, k));
    }
}

Python3

def maxSum(arr, n, k):
    # DP table
    dp = [0] * n
 
    # Computing the DP table
    for i in range(n):
        tot = 0
        for j in range(i - k, i):
            if j >= 0:
                tot = max(tot, dp[j])
        dp[i] = tot + arr[i]
 
    # Returning the maximum sum
    res = 0
    for i in range(n):
        res = max(res, dp[i])
 
    # return final ans
    return res
 
 
# Driver code
arr = [-1, 2, -3, 4, 5]
k = 2
n = len(arr)
print(maxSum(arr, n, k))

C#

using System;
 
class MaxSum
{
    static int ComputeMaxSum(int[] arr, int n, int k)
    {
        // DP table
        int[] dp = new int[n];
 
        // Computing the DP table
        for (int i = 0; i < n; i++)
        {
            int tot = 0;
            for (int j = i - k; j < i; j++)
            {
                if (j >= 0)
                {
                    tot = Math.Max(tot, dp[j]);
                }
            }
            dp[i] = tot + arr[i];
        }
 
        // Returning the maximum sum
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            res = Math.Max(res, dp[i]);
        }
 
        // return final ans
        return res;
    }
 
    static void Main()
    {
        int[] arr = {-1, 2, -3, 4, 5};
        int k = 2;
        int n = arr.Length;
        Console.WriteLine(ComputeMaxSum(arr, n, k));
    }
}

Javascript

// Function to find the maximum sum subsequence
// such that no two elements are adjacent
function maxSum(arr, n, k)
{
    // DP table
    let dp = new Array(n);
     
    // Initializing the DP table
    dp.fill(0);
     
    // Computing the DP table
    for (let i = 0; i < n; i++) {
        let tot = 0;
        for (let j = i - k; j < i; j++) {
            if (j >= 0)
                tot = Math.max(tot, dp[j]);
        }
        dp[i] = tot + arr[i];
    }
     
    // Returning the maximum sum
    let res = 0;
    for (let i = 0; i < n; i++)
        res = Math.max(res, dp[i]);
         
    // return final ans
    return res;
}
 
// Driver code
function main()
{
    // Input array
    let arr = [ -1, 2, -3, 4, 5 ];
     
    let k = 2;
     
    let n = arr.length;
     
    console.log(maxSum(arr, n, k));
}
 
main();

Output

Time Complexity: O(n*k)
Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!