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 subarrayint 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 codeint 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 approachimport 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 subarraydef 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 codeif __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 approachusing 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> |
Output
11
Time Complexity: O(N)
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!