以前做OJ的时候都想不通为什么是DP，现在终于搞明白了。
一开始想的时候，想着 dp[i] 为下标0~i元素最大的字串和。
dp[i] = max { dp[i-1] a[i]不在subarry中
dp[i-1]+ a[i] 在subarray中 承接之前的subarray
a[i] } 在subarray中 新开一个subarray
这个状态转移方程是有问题的，因为没法确定dp[i-1]是否在subarray中，所以dp[i-1]+ a[i]这里是不对的。
因此直接一步到位解这个问题是不行的。根据上述分析，可以把问题拆分成两部分：
dp[i] 表示以a[i]结尾的最大子串和，maxsum[i] 表示下标0~i元素所包括的最大子串和。
dp[0]=a[0], maxsum[0]=a[0];
dp[i] = max{ dp[i-1]+a[i] 承接之前的subarray
a[i] } 新开一个subarray
maxsum[i] = max{ maxsum[i-1] subarray不包括a[i]
dp[i] } subarray包括a[i]
实际上就是把最开始的思路分成了两步。由于dp[i]和maxsum[i]求解的过程中都只依赖上一个状态的元素，因此空间复杂度可以从O(n)降到O(1)。
原文：https://www.cnblogs.com/hankunyan/p/8979632.html