Given an integer array arr[] of length N and an integer K, the task is to select some non-overlapping sub-arrays such that each sub-array is exactly of length K, no two sub-arrays are adjacent and sum of all the elements of the selected sub-arrays is maximum.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}, K = 2
Output: 12
Sub-arrays that maximizes sum will be {{1, 2}, {4, 5}}.
Thus, the answer will be 12.
Input: arr[] = {1, 1, 1, 1, 1}, K = 1
Output: 3
Approach: This problem can be solved using 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 arr[i…n-1] satisfying above conditions.
We will have two possible choices i.e. select the sub-array arr[i…i+k-1] and solve for dp[i + k + 1] or reject it and solve for dp[i + 1].
Thus, recurrence relation will be
dp[i] = max(dp[i + 1], arr[i] + arr[i + 1] + arr[i + 2] + … + arr[i + k – 1] + dp[i + k + 1])
Since, the values of K can be large, we will use prefix-sum array to find the sum of all the elements of the sub-array arr[i…i + k – 1] in O(1).
Overall, time complexity of the algorithm will be O(N).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>#define maxLen 10using namespace std;// To store the states of dpint dp[maxLen];// To check if a given state// has been solvedbool v[maxLen];// To store the prefix-sumint prefix_sum[maxLen];// Function to fill the prefix_sum[] with// the prefix sum of the given arrayvoid findPrefixSum(int arr[], int n){ prefix_sum[0] = arr[0]; for (int i = 1; i < n; i++) prefix_sum[i] = arr[i] + prefix_sum[i - 1];}// 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 + k > n) return 0; // To check if a state has // been solved if (v[i]) return dp[i]; v[i] = 1; int x; if (i == 0) x = prefix_sum[k - 1]; else x = prefix_sum[i + k - 1] - prefix_sum[i - 1]; // Required recurrence relation dp[i] = max(maxSum(arr, i + 1, n, k), x + maxSum(arr, i + k + 1, n, k)); // Returning the value return dp[i];}// Driver codeint main(){ int arr[] = { 1, 3, 7, 6 }; int n = sizeof(arr) / sizeof(int); int k = 1; // Finding prefix-sum findPrefixSum(arr, n); // Finding the maximum possible sum cout << maxSum(arr, 0, n, k); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG { static int maxLen = 10; // To store the states of dp static int[] dp = new int[maxLen]; // To check if a given state // has been solved static boolean[] v = new boolean[maxLen]; // To store the prefix-sum static int[] prefix_sum = new int[maxLen]; // Function to fill the prefix_sum[] with // the prefix sum of the given array static void findPrefixSum(int arr[], int n) { prefix_sum[0] = arr[0]; for (int i = 1; i < n; i++) { prefix_sum[i] = arr[i] + prefix_sum[i - 1]; } } // 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 + k > n) { return 0; } // To check if a state has // been solved if (v[i]) { return dp[i]; } v[i] = true; int x; if (i == 0) { x = prefix_sum[k - 1]; } else { x = prefix_sum[i + k - 1] - prefix_sum[i - 1]; } // Required recurrence relation dp[i] = Math.max(maxSum(arr, i + 1, n, k), x + maxSum(arr, i + k + 1, n, k)); // Returning the value return dp[i]; } // Driver code public static void main(String[] args) { int arr[] = {1, 3, 7, 6}; int n = arr.length; int k = 1; // Finding prefix-sum findPrefixSum(arr, n); // Finding the maximum possible sum System.out.println(maxSum(arr, 0, n, k)); }}// This code contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach maxLen = 10# To store the states of dp dp = [0]*maxLen; # To check if a given state # has been solved v = [0]*maxLen; # To store the prefix-sum prefix_sum = [0]*maxLen; # Function to fill the prefix_sum[] with # the prefix sum of the given array def findPrefixSum(arr, n) : prefix_sum[0] = arr[0]; for i in range(n) : prefix_sum[i] = arr[i] + prefix_sum[i - 1]; # Function to find the maximum sum subsequence # such that no two elements are adjacent def maxSum(arr, i, n, k) : # Base case if (i + k > n) : return 0; # To check if a state has # been solved if (v[i]) : return dp[i]; v[i] = 1; if (i == 0) : x = prefix_sum[k - 1]; else : x = prefix_sum[i + k - 1] - prefix_sum[i - 1]; # Required recurrence relation dp[i] = max(maxSum(arr, i + 1, n, k), x + maxSum(arr, i + k + 1, n, k)); # Returning the value return dp[i]; # Driver code if __name__ == "__main__" : arr = [ 1, 3, 7, 6 ]; n = len(arr); k = 1; # Finding prefix-sum findPrefixSum(arr, n); # Finding the maximum possible sum print(maxSum(arr, 0, n, k)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;class GFG { static int maxLen = 10; // To store the states of dp static int[] dp = new int[maxLen]; // To check if a given state // has been solved static bool[] v = new bool[maxLen]; // To store the prefix-sum static int[] prefix_sum = new int[maxLen]; // Function to fill the prefix_sum[] with // the prefix sum of the given array static void findPrefixSum(int []arr, int n) { prefix_sum[0] = arr[0]; for (int i = 1; i < n; i++) { prefix_sum[i] = arr[i] + prefix_sum[i - 1]; } } // 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 + k > n) { return 0; } // To check if a state has // been solved if (v[i]) { return dp[i]; } v[i] = true; int x; if (i == 0) { x = prefix_sum[k - 1]; } else { x = prefix_sum[i + k - 1] - prefix_sum[i - 1]; } // Required recurrence relation dp[i] = Math.Max(maxSum(arr, i + 1, n, k), x + maxSum(arr, i + k + 1, n, k)); // Returning the value return dp[i]; } // Driver code public static void Main(String[] args) { int []arr = {1, 3, 7, 6}; int n = arr.Length; int k = 1; // Finding prefix-sum findPrefixSum(arr, n); // Finding the maximum possible sum Console.Write(maxSum(arr, 0, n, k)); } } // This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation of the approachvar maxLen = 10// To store the states of dpvar dp = Array(maxLen);// To check if a given state// has been solvedvar v = Array(maxLen);// To store the prefix-sumvar prefix_sum = Array(maxLen);;// Function to fill the prefix_sum[] with// the prefix sum of the given arrayfunction findPrefixSum(arr, n){ prefix_sum[0] = arr[0]; for (var i = 1; i < n; i++) prefix_sum[i] = arr[i] + prefix_sum[i - 1];}// Function to find the maximum sum subsequence// such that no two elements are adjacentfunction maxSum(arr, i, n, k){ // Base case if (i + k > n) return 0; // To check if a state has // been solved if (v[i]) return dp[i]; v[i] = 1; var x; if (i == 0) x = prefix_sum[k - 1]; else x = prefix_sum[i + k - 1] - prefix_sum[i - 1]; // Required recurrence relation dp[i] = Math.max(maxSum(arr, i + 1, n, k), x + maxSum(arr, i + k + 1, n, k)); // Returning the value return dp[i];}// Driver codevar arr = [1, 3, 7, 6];var n = arr.length;var k = 1;// Finding prefix-sumfindPrefixSum(arr, n);// Finding the maximum possible sumdocument.write( maxSum(arr, 0, n, k));</script> |
Output:
9
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!
