Maximum sum two non-overlapping subarrays of given size
Given an array, we need to find two subarrays with a specific length K such that sum of these subarrays is maximum among all possible choices of subarrays.
Examples:
Input : arr[] = [2, 5, 1, 2, 7, 3, 0] K = 2 Output : 2 5 7 3 We can choose two arrays of maximum sum as [2, 5] and [7, 3], the sum of these two subarrays is maximum among all possible choices of subarrays of length 2. Input : arr[] = {10, 1, 3, 15, 30, 40, 4, 50, 2, 1} K = 3 Output : 3 15 30 40 4 50
We can solve this problem similar to two pointers method. First we store the prefix sum in a separate array so that any subarray sum can be calculated in constant time. After that we will initialize our two subarray from (N – 2K) and (N – K) indices, where N is the length of the array and K is required subarray length. Then we will move from (N – 2K) index towards 0 and each time we will check whether subarray sum at current index and subarray sum at (current index + K) is greater than previously chosen subarray or not if they are, then update the summation. We can see here that as we need to maximize our sum, we can treat both subarrays independently. At each index we will check subarray sum at current index and subarray sum at K distance away and we will choose maximum sum independently and update the final answer as summation of both these array. In below code index is also taken with sum in form of a pair to actually print the subarrays. Total time complexity of solution will be linear.
Please see below code for better understanding.
Implementation:
C++
// C++ program to get maximum sum two non-overlapping // subarrays of same specified length #include <bits/stdc++.h> using namespace std; // Utility method to get sum of subarray // from index i to j int getSubarraySum( int sum[], int i, int j) { if (i == 0) return sum[j]; else return (sum[j] - sum[i - 1]); } // Method prints two non-overlapping subarrays of // length K whose sum is maximum void maximumSumTwoNonOverlappingSubarray( int arr[], int N, int K) { int sum[N]; // filling prefix sum array sum[0] = arr[0]; for ( int i = 1; i < N; i++) sum[i] = sum[i - 1] + arr[i]; // initializing subarrays from (N-2K) and (N-K) indices pair< int , int > resIndex = make_pair(N - 2 * K, N - K); // initializing result sum from above subarray sums int maxSum2Subarray = getSubarraySum(sum, N - 2 * K, N - K - 1) + getSubarraySum(sum, N - K, N - 1); // storing second subarray maximum and its starting index pair< int , int > secondSubarrayMax = make_pair(N - K, getSubarraySum(sum, N - K, N - 1)); // looping from N-2K-1 towards 0 for ( int i = N - 2 * K - 1; i >= 0; i--) { // get subarray sum from (current index + K) int cur = getSubarraySum(sum, i + K, i + 2 * K - 1); // if (current index + K) sum is more then update // secondSubarrayMax if (cur >= secondSubarrayMax.second) secondSubarrayMax = make_pair(i + K, cur); // now getting complete sum (sum of both subarrays) cur = getSubarraySum(sum, i, i + K - 1) + secondSubarrayMax.second; // if it is more then update main result if (cur >= maxSum2Subarray) { maxSum2Subarray = cur; resIndex = make_pair(i, secondSubarrayMax.first); } } // printing actual subarrays for ( int i = resIndex.first; i < resIndex.first + K; i++) cout << arr[i] << " " ; cout << endl; for ( int i = resIndex.second; i < resIndex.second + K; i++) cout << arr[i] << " " ; cout << endl; } // Driver code to test above methods int main() { int arr[] = {2, 5, 1, 2, 7, 3, 0}; int N = sizeof (arr) / sizeof ( int ); // K will be given such that (N >= 2K) int K = 2; maximumSumTwoNonOverlappingSubarray(arr, N, K); return 0; } |
Java
// Java program to get maximum sum two non-overlapping // subarrays of same specified length class GFG { static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Utility method to get sum of subarray // from index i to j static int getSubarraySum( int sum[], int i, int j) { if (i == 0 ) return sum[j]; else return (sum[j] - sum[i - 1 ]); } // Method prints two non-overlapping subarrays of // length K whose sum is maximum static void maximumSumTwoNonOverlappingSubarray( int arr[], int N, int K) { int []sum = new int [N]; // filling prefix sum array sum[ 0 ] = arr[ 0 ]; for ( int i = 1 ; i < N; i++) sum[i] = sum[i - 1 ] + arr[i]; // initializing subarrays from // (N-2K) and (N-K) indices pair resIndex = new pair(N - 2 * K, N - K); // initializing result sum from above subarray sums int maxSum2Subarray = getSubarraySum(sum, N - 2 * K, N - K - 1 ) + getSubarraySum(sum, N - K, N - 1 ); // storing second subarray maximum and // its starting index pair secondSubarrayMax = new pair(N - K, getSubarraySum(sum, N - K, N - 1 )); // looping from N-2K-1 towards 0 for ( int i = N - 2 * K - 1 ; i >= 0 ; i--) { // get subarray sum from (current index + K) int cur = getSubarraySum(sum, i + K, i + 2 * K - 1 ); // if (current index + K) sum is more // then update secondSubarrayMax if (cur >= secondSubarrayMax.second) secondSubarrayMax = new pair(i + K, cur); // now getting complete sum (sum of both subarrays) cur = getSubarraySum(sum, i, i + K - 1 ) + secondSubarrayMax.second; // if it is more then update main result if (cur >= maxSum2Subarray) { maxSum2Subarray = cur; resIndex = new pair(i, secondSubarrayMax.first); } } // printing actual subarrays for ( int i = resIndex.first; i < resIndex.first + K; i++) System.out.print(arr[i] + " " ); System.out.println(); for ( int i = resIndex.second; i < resIndex.second + K; i++) System.out.print(arr[i] + " " ); System.out.println(); } // Driver code to test above methods public static void main(String[] args) { int arr[] = { 2 , 5 , 1 , 2 , 7 , 3 , 0 }; int N = arr.length; // K will be given such that (N >= 2K) int K = 2 ; maximumSumTwoNonOverlappingSubarray(arr, N, K); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to get maximum Sum two # non-overlapping subarrays of same specified length # Utility method to get Sum of # subarray from index i to j def getSubarraySum( Sum , i, j): if i = = 0 : return Sum [j] else : return Sum [j] - Sum [i - 1 ] # Method prints two non-overlapping subarrays # of length K whose Sum is maximum def maximumSumTwoNonOverlappingSubarray(arr, N, K): Sum = [ None ] * N # filling prefix Sum array Sum [ 0 ] = arr[ 0 ] for i in range ( 1 , N): Sum [i] = Sum [i - 1 ] + arr[i] # Initializing subarrays from # (N-2K) and (N-K) indices resIndex = (N - 2 * K, N - K) # initializing result Sum from above subarray Sums maxSum2Subarray = (getSubarraySum( Sum , N - 2 * K, N - K - 1 ) + getSubarraySum( Sum , N - K, N - 1 )) # storing second subarray maximum and its starting index secondSubarrayMax = (N - K, getSubarraySum( Sum , N - K, N - 1 )) # looping from N-2K-1 towards 0 for i in range (N - 2 * K - 1 , - 1 , - 1 ): # get subarray Sum from (current index + K) cur = getSubarraySum( Sum , i + K, i + 2 * K - 1 ) # if (current index + K) Sum is more # than update secondSubarrayMax if cur > = secondSubarrayMax[ 1 ]: secondSubarrayMax = (i + K, cur) # now getting complete Sum (Sum of both subarrays) cur = (getSubarraySum( Sum , i, i + K - 1 ) + secondSubarrayMax[ 1 ]) # If it is more then update main result if cur > = maxSum2Subarray: maxSum2Subarray = cur resIndex = (i, secondSubarrayMax[ 0 ]) # printing actual subarrays for i in range (resIndex[ 0 ], resIndex[ 0 ] + K): print (arr[i], end = " " ) print () for i in range (resIndex[ 1 ], resIndex[ 1 ] + K): print (arr[i], end = " " ) print () # Driver Code if __name__ = = "__main__" : arr = [ 2 , 5 , 1 , 2 , 7 , 3 , 0 ] N = len (arr) # K will be given such that (N >= 2K) K = 2 maximumSumTwoNonOverlappingSubarray(arr, N, K) # This code is contributed by Rituraj Jain |
C#
// C# program to get maximum sum two non-overlapping // subarrays of same specified length using System; class GFG { class pair { public int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Utility method to get sum of subarray // from index i to j static int getSubarraySum( int []sum, int i, int j) { if (i == 0) return sum[j]; else return (sum[j] - sum[i - 1]); } // Method prints two non-overlapping subarrays of // length K whose sum is maximum static void maximumSumTwoNonOverlappingSubarray( int []arr, int N, int K) { int []sum = new int [N]; // filling prefix sum array sum[0] = arr[0]; for ( int i = 1; i < N; i++) sum[i] = sum[i - 1] + arr[i]; // initializing subarrays from // (N-2K) and (N-K) indices pair resIndex = new pair(N - 2 * K, N - K); // initializing result sum from above subarray sums int maxSum2Subarray = getSubarraySum(sum, N - 2 * K, N - K - 1) + getSubarraySum(sum, N - K, N - 1); // storing second subarray maximum and // its starting index pair secondSubarrayMax = new pair(N - K, getSubarraySum(sum, N - K, N - 1)); // looping from N-2K-1 towards 0 for ( int i = N - 2 * K - 1; i >= 0; i--) { // get subarray sum from (current index + K) int cur = getSubarraySum(sum, i + K, i + 2 * K - 1); // if (current index + K) sum is more // then update secondSubarrayMax if (cur >= secondSubarrayMax.second) secondSubarrayMax = new pair(i + K, cur); // now getting complete sum (sum of both subarrays) cur = getSubarraySum(sum, i, i + K - 1) + secondSubarrayMax.second; // if it is more then update main result if (cur >= maxSum2Subarray) { maxSum2Subarray = cur; resIndex = new pair(i, secondSubarrayMax.first); } } // printing actual subarrays for ( int i = resIndex.first; i < resIndex.first + K; i++) Console.Write(arr[i] + " " ); Console.WriteLine(); for ( int i = resIndex.second; i < resIndex.second + K; i++) Console.Write(arr[i] + " " ); Console.WriteLine(); } // Driver code public static void Main(String[] args) { int []arr = {2, 5, 1, 2, 7, 3, 0}; int N = arr.Length; // K will be given such that (N >= 2K) int K = 2; maximumSumTwoNonOverlappingSubarray(arr, N, K); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to get maximum sum two non-overlapping // subarrays of same specified length // Utility method to get sum of subarray // from index i to j function getSubarraySum(sum, i, j) { if (i == 0) return sum[j]; else return (sum[j] - sum[i - 1]); } // Method prints two non-overlapping subarrays of // length K whose sum is maximum function maximumSumTwoNonOverlappingSubarray(arr, N, K) { let sum = new Array(N); // filling prefix sum array sum[0] = arr[0]; for (let i = 1; i < N; i++) sum[i] = sum[i - 1] + arr[i]; // initializing subarrays from (N-2K) and (N-K) indices let resIndex = [N - 2 * K, N - K]; // initializing result sum from above subarray sums let maxSum2Subarray = getSubarraySum(sum, N - 2 * K, N - K - 1) + getSubarraySum(sum, N - K, N - 1); // storing second subarray maximum and its starting index let secondSubarrayMax = [N - K, getSubarraySum(sum, N - K, N - 1)]; // looping from N-2K-1 towards 0 for (let i = N - 2 * K - 1; i >= 0; i--) { // get subarray sum from (current index + K) let cur = getSubarraySum(sum, i + K, i + 2 * K - 1); // if (current index + K) sum is more then update // secondSubarrayMax if (cur >= secondSubarrayMax[1]) secondSubarrayMax = [i + K, cur]; // now getting complete sum (sum of both subarrays) cur = getSubarraySum(sum, i, i + K - 1) + secondSubarrayMax[1]; // if it is more then update main result if (cur >= maxSum2Subarray) { maxSum2Subarray = cur; resIndex = [i, secondSubarrayMax[0]]; } } // printing actual subarrays for (let i = resIndex[0]; i < resIndex[0] + K; i++) document.write(arr[i] + " " ); document.write( "<br>" ); for (let i = resIndex[1]; i < resIndex[1] + K; i++) document.write(arr[i] + " " ); document.write( "<br>" ); } // Driver code to test above methods let arr = [2, 5, 1, 2, 7, 3, 0]; let N = arr.length; // K will be given such that (N >= 2K) let K = 2; maximumSumTwoNonOverlappingSubarray(arr, N, K); </script> |
2 5 7 3
Time Complexity: O(n) , where n is the size of the given array.
Auxiliary Space: O(n)