Maximum Sum of Two Non-Overlapping Subarrays of any length

Question

I see "Maximum Sum of Two Non-Overlapping Subarrays (of specific given lengths and the array contains only positive numbers)" from Leetcode https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/.

But I encountered a variation of this problem - "Maximum Sum of Two Non-Overlapping Subarrays (of any length) and the array contains both positive and negative numbers". I don't see any coding platform having this problem for me to confirm my solution.

My Theoretical Solution:

1. Create a new array named "maxSumAtIndex"and insert the maximum possible sum at each index. i.e if the previous index's value plus current index's value is greater than current index's value, insert that value in current index or else just the current index's value. (like Kadane's)

2. Find the index of maximum value in the array "maxSumAtIndex" (say index 10). From that index traverse back (towards index 0) and get the index of second highest value (say index 7). The sum of the values between these 2 indices (7 and 10) in the original array will give the sum from one of the subarrays.

3. The other subarray lies somewhere between 0-6 or 11-20. Find which of these 2 sub arrays has the maximum value in the array "maxSumAtIndex" (say index 18). From that index(18) traverse back until index 11 and find the index of second highest value between 11-20 (say index 12). The sum of the values between these 2 indices (12 and 18) in the original array will give the sum from the 2nd subarray.

4. finalSum = sum from step (2) + sum from step (3)

Questions:

1. If there is any platform having this question, I would like to know.

2. I ran the above solution against a couple of self made test cases and it seemed to work. Though I can see a pattern that this may work, I am not able to figure out why it works (like a layman proof). Is this solution right and if it is , why it works ?

   -9 5 -9 -8 [9 7] -10 [10 9] = 35

   -9 5 -4 -8 9 16 6 16 25

Highest 25 at index 8. Second Highest 16 at index 7 (first occurence). Summing index 7 to index 8 from original array -> 10 + 9 = 19

Highest 16 at index 5. Second Highest 9 at index 4. Summing index 4 to index 5 from original array -> 9 + 7 = 16

19 + 16 = 35

3. Is there a better solution ?

Answer 1

I don't see any reason to believe that your algorithm works, but a simple algorithm that does work is to run Kadane's algorithm to find largest-sum subarray before each position, and then run Kadane's algorithm backwards to find the largest sum subarray after each position.

Since disjoint subarrays must be on either side of some position, then just check all the positions to find the largest sum of the largest-sum arrays before and after.

Answer 2

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin>>n;
    vector<int>nums(n);
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }
    vector<int>aagesekadane; //aagesekadane <=>kadaneFromFront 
    vector<int>pichesekadane(n);  //pichesekadane <=>kadaneFromBack
    int cs=0;
    int ca=0;
    aagesekadane.push_back(0);
    pichesekadane.push_back(0);
    for(int i=0;i<nums.size();i++){
        cs+=nums[i];
        if(cs>ca){
            ca=cs;
        }
        if(cs<0)cs=0;
        aagesekadane.push_back(ca);
    }
    cs=0;
    ca=0;
    for(int i=nums.size()-1;i>=0;i--){
        cs+=nums[i];
        if(cs>ca){
            ca=cs;
        }
        if(cs<0)cs=0;
        pichesekadane[i]=ca;
    }
    
    int ans=0;
    for(int i=0;i<=n;i++){
            ans=max(ans,aagesekadane[i]+pichesekadane[i]);
        
    }
cout<<ans<<endl;
}
int main() {
    int t;
    cin>>t;
    while(t--){
    solve();
    }
    return 0;
}

Hope this works

Answer 3

I used both approach for solving Max sum of 2 non overlapping subarray of any length.

1. Using kadanes for left part and right part of current index and storing the max answer of it till end. Eg :- arr = [2, 5, -1, 4, 0] If i am currently at 2 index i.e. at -1 value,then take the max sum subarray at left side of index 2 and same for right side of index 2. At every index take the maximum sum by taking left+right and comparing with some Maxx variable to get overall max value. T.C. O(n^2)

2. Do forward loop of an main array and store maximum sum subarray at every index in left array. And do same procedure but from back side of an main array and store in right array from last position. Now, iterate through left and right and take max(Maxx, left[i]+right[i]). You will get your answer

Hope this will help.

Answer 4

#include <bits/stdc++.h>
using namespace std;

//for the case when subarray size can be zero 

int maxSubArraySum(vector<int> arr, int start, int end)
{
    int max_so_far = arr[start], curr_max = arr[start];

    for (int i = start + 1; i < end; i++)
    {
        curr_max = max(arr[i], curr_max + arr[i]);
        max_so_far = max(max_so_far, curr_max);
    }
    return max_so_far > 0 ? max_so_far : 0;
}
int main()
{
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i=0; i<n, i++)
    {
        cin >> arr[i];
    }
    int ans = 0;
    for(int i=0; i<n, i++)
    {
        int a = maxSubArraySum(arr, 0, i);
        int b = maxSubArraySum(arr, i, n);
        ans = max(ans, a + b);
    }
    cout << ans;
    return 0;
}