In the Java edition of EPI page 264 is the DP approach for the max subarray sum. I don’t get the logic. You are using the summation formula and state at any index j the max subarray sum is
S[j] - minS[k] (where k <= j)
Why is this correct? Going over the code in that page for the array eg [-5, -3] the max subarray sum is calculated as 0 and not -3. Why?
Could you please elaborate on the logic of why we subtract with S[k]?
Thank you