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(2N)
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 10using namespace std;// Variable to store states of dpint dp[maxLen];// Variable to check if a given state has been solvedbool visit[maxLen];// Function to find the maximum sum subsequence// such that no two elements are adjacentint 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 codeint 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 approachimport 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 approachusing System;class GFG{static int maxLen = 10;// Variable to store states of dpstatic int []dp = new int[maxLen];// Variable to check // if a given state has been solvedstatic bool []visit = new bool[maxLen];// Function to find the maximum sum subsequence// such that no two elements are adjacentstatic 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 codestatic 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:
11
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 10using namespace std;// Function to find the maximum sum subsequence// such that no two elements are adjacentint 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 codeint 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 codearr = [-1, 2, -3, 4, 5]k = 2n = 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 adjacentfunction 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 codefunction 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
11
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
