title: Maximum Sum of Two Non-Overlapping Subarrays of any length
body: <p>I see &quot;Maximum Sum of Two Non-Overlapping Subarrays (of specific given lengths and the array contains only positive numbers)&quot; from Leetcode
  <a href="https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/" rel="nofollow noreferrer">https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/</a>.</p>
  <p>But I encountered a variation of this problem - &quot;Maximum Sum of Two Non-Overlapping Subarrays (of any length) and the array contains both positive and negative numbers&quot;. I don't see any coding platform having this problem for me to confirm my solution.</p>
  <p><strong>My Theoretical Solution:</strong></p>
  <ol>
  <li><p>Create a new array named &quot;maxSumAtIndex&quot;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)</p>
  </li>
  <li><p>Find the index of maximum value in the array &quot;maxSumAtIndex&quot; (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.</p>
  </li>
  <li><p>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 &quot;maxSumAtIndex&quot; (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.</p>
  </li>
  <li><p>finalSum = sum from step (2) + sum from step (3)</p>
  </li>
  </ol>
  <p><strong>Questions:</strong></p>
  <ol>
  <li><p>If there is any platform having this question, I would like to know.</p>
  </li>
  <li><p>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 ?</p>
  <p>-9 5 -9 -8 [9 7] -10 [10 9] = 35</p>
  <p>-9 5 -4  -8 9 16 6 16 25</p>
  </li>
  </ol>
  <p>Highest 25 at index 8. Second Highest 16 at index 7 (first occurence).
  Summing index 7 to index 8 from original array -&gt; 10 + 9 = 19</p>
  <p>Highest 16 at index 5. Second Highest 9 at index 4.
  Summing index 4 to index 5 from original array -&gt; 9 + 7 = 16</p>
  <p>19 + 16 = 35</p>
  <ol start="3">
  <li>Is there a better solution ?</li>
  </ol>