Maximum sum subarray - python

#1

So in the book, in dynamic programming - a problem for maximum sum subarray is solved like this

Maximum Sum Ending at j = S( j ) - min k < j (S(k))

The question is why? Explanation is not clear to me. Subtracting some minimum sum - how can it lead to maximum sum?

0 Likes
#2

Hi @sha256pki,

The idea is pretty straightforward, we have the accumulate sum array which sum everything from A[0] to A[i] for whatever i you choose. Then the maximum sum subarray ending at A[i] will basically the accumulate sum subarray from A[0] to A[i] minus the minimum accumulate sum subarray from A[0] to A[j] if j < i.

0 Likes
#3

Hi @tsunghsienlee, I understand that it works. But I still don’t understand how it works. Why does subtracting the min subarray sum yield the max sum?

0 Likes