arraysalgorithmdata-structuresdynamic-programmingkadanes-algorithm

Maximum Sum of Two Non-Overlapping Subarrays of any length

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

  1. Is there a better solution ?
Solution

  • 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.