Maximum Sum of two non-overlapping Subarrays of any length
Given an array A consisting of N integers, the task is to find the maximum sum of two non-overlapping subarrays of any length of the array.
Note: You can select empty subarrays also.
Examples:
Input: N = 3, A[] = {-4, -5, -2}
Output: 0
Explanation: Two empty subarrays are optimal with maximum sum = 0.Input: N = 5, A[] = {5, -2, 3, -6, 5}
Output: 11
Explanation: Optimal subarrays are {5, -2, 3} and {5} with maximum sum = 11.
Approach: To solve the problem follow the below idea:
This problem can be thought of as the maximum sum contiguous subarray (Kadane’s Algorithm) from both left and right directions.
By applying this algorithm, we are ensuring a maximum contiguous sum up to an index that can be stored in two vectors from front and back for finding maximum non-intersecting sum.
Follow the given steps to solve the problem:
- Initialize two vectors frontKadane and backKadane with 0.
- Traverse array A and implement Kadane Algorithm from left to right and store the maximum subarray sum in frontKadane[i].
- Traverse array A and implement Kadane Algorithm from right to left and store the maximum subarray sum in backKadane[i].
- Traverse from 0 to N and calculate maximum value of (frontKadane[i] + backKadane[i]) and store in the variable result.
- Return the result as the final answer.
Below is the implementation for the above approach:
C++14
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; typedef long long ll; // Function to find the maximum sum // of two non-overlapping subarray int maxNonIntersectSum( int * A, int & N) { vector< int > frontKadane; vector< int > backKadane(N); int sum1 = 0, sum2 = 0, result = 0; frontKadane.push_back(0); backKadane.push_back(0); // Loop to calculate the // maximum subarray sum till ith index for ( int i = 0; i < N; i++) { sum1 += A[i]; sum2 = max(sum1, sum2); sum1 = max(sum1, 0); frontKadane.push_back(sum2); } sum1 = 0; sum2 = 0; // Loop to calculate the // maximum subarray sum till ith index for ( int i = N - 1; i >= 0; i--) { sum1 += A[i]; sum2 = max(sum1, sum2); sum1 = max(sum1, 0); backKadane[i] = sum2; } for ( int i = 0; i <= N; i++) result = max(result, backKadane[i] + frontKadane[i]); // Return the maximum // non-overlapping subarray sum return result; } // Driver code int main() { int A[] = { 5, -2, 3, -6, 5 }; int N = sizeof (A) / sizeof (A[0]); // Function call cout << maxNonIntersectSum(A, N); return 0; } |
Java
// Java code for the above approach import java.io.*; class GFG { // Function to find the maximum sum of two // non-overlapping subarray static int maxNonIntersect( int [] A, int N) { int [] frontKadane = new int [N]; int [] backKadane = new int [N]; int sum1 = 0 , sum2 = 0 , result = 0 ; // Loop to calculate the maximum subarray sum till // ith index for ( int i = 0 ; i < N; i++) { sum1 += A[i]; sum2 = Math.max(sum1, sum2); sum1 = Math.max(sum1, 0 ); frontKadane[i] = sum2; } sum1 = 0 ; sum2 = 0 ; // Loop to calculate the maximum subarray sum till // ith index for ( int i = N - 1 ; i >= 0 ; i--) { sum1 += A[i]; sum2 = Math.max(sum1, sum2); sum1 = Math.max(sum1, 0 ); backKadane[i] = sum2; } for ( int i = 0 ; i < N; i++) { result = Math.max(result, backKadane[i] + frontKadane[i]); } // Return the maximum non-overlapping subarray sum return result; } public static void main(String[] args) { int [] A = { 5 , - 2 , 3 , - 6 , 5 }; int N = A.length; // Function call System.out.print(maxNonIntersect(A, N)); } } // This code is contributed by lokesh (lokeshmvs21). |
Python3
# Python3 code for the above approach: # Function to find the maximum sum # of two non-overlapping subarray def maxNonIntersectSum(A, N): frontKadane = [] backKadane = [ 0 ] * N sum1 = 0 sum2 = 0 result = 0 frontKadane.append( 0 ) backKadane.append( 0 ) # Loop to calculate the # maximum subarray sum till ith index for i in range (N): sum1 + = A[i] sum2 = max (sum1, sum2) sum1 = max (sum1, 0 ) frontKadane.append(sum2) sum1 = 0 sum2 = 0 # Loop to calculate the # maximum subarray sum till ith index for i in range (N - 1 , 0 , - 1 ): sum1 + = A[i] sum2 = max (sum1, sum2) sum1 = max (sum1, 0 ) backKadane[i] = sum2 for i in range (N + 1 ): result = max (result, backKadane[i] + frontKadane[i]) # Return the maximum # non-overlapping subarray sum return result # Driver code if __name__ = = "__main__" : A = [ 5 , - 2 , 3 , - 6 , 5 ] N = len (A) # Function call print (maxNonIntersectSum(A, N)) # This code is contributed by Rohit Pradhan |
C#
// C# code for the above approach using System; public class GFG { // Function to find the maximum sum of two // non-overlapping subarray static int maxNonIntersect( int [] A, int N) { int [] frontKadane = new int [N]; int [] backKadane = new int [N]; int sum1 = 0, sum2 = 0, result = 0; // Loop to calculate the maximum subarray sum till // ith index for ( int i = 0; i < N; i++) { sum1 += A[i]; sum2 = Math.Max(sum1, sum2); sum1 = Math.Max(sum1, 0); frontKadane[i] = sum2; } sum1 = 0; sum2 = 0; // Loop to calculate the maximum subarray sum till // ith index for ( int i = N - 1; i >= 0; i--) { sum1 += A[i]; sum2 = Math.Max(sum1, sum2); sum1 = Math.Max(sum1, 0); backKadane[i] = sum2; } for ( int i = 0; i < N; i++) { result = Math.Max(result, backKadane[i] + frontKadane[i]); } // Return the maximum non-overlapping subarray sum return result; } public static void Main( string [] args) { int [] A = { 5, -2, 3, -6, 5 }; int N = A.Length; // Function call Console.Write(maxNonIntersect(A, N)); } } // This code is contributed by AnkThon |
Javascript
<script> // JavaScript program for above approach: // Function to find the maximum sum of two // non-overlapping subarray function maxNonletersect(A, N) { let frontKadane = new Array(N); let backKadane = new Array(N); let sum1 = 0, sum2 = 0, result = 0; // Loop to calculate the maximum subarray sum till // ith index for (let i = 0; i < N; i++) { sum1 += A[i]; sum2 = Math.max(sum1, sum2); sum1 = Math.max(sum1, 0); frontKadane[i] = sum2; } sum1 = 0; sum2 = 0; // Loop to calculate the maximum subarray sum till // ith index for (let i = N - 1; i >= 0; i--) { sum1 += A[i]; sum2 = Math.max(sum1, sum2); sum1 = Math.max(sum1, 0); backKadane[i] = sum2; } for (let i = 0; i < N; i++) { result = Math.max(result, backKadane[i] + frontKadane[i]); } // Return the maximum non-overlapping subarray sum return result; } // Driver Code let A = [ 5, -2, 3, -6, 5 ]; let N = A.length; // Function call document.write(maxNonletersect(A, N)); // This code is contributed by code_hunt. </script> |
11
Time Complexity: O(N)
Auxiliary Space: O(N)