当我第一次看到c(i) = max{c(i-1) + a[i], a[i]}时，一脸懵逼
示例：[4, 4, -4, -4, 2, 100]
c(5) = max{c(4) + a[5], a[5]} = max{8+100, 100} = 108
但是真正的c(5) = 102。
我当时是把c(i)理解错了。以为是子序列[0..i]的子序列的最大和。
子序列[0..4]的最大和子序列是[4, 4]，则和是8
子序列[0..5]的最大和子序列是[2, 100]，则和是102
上面的是错误的理解。
下面是正确的理解。
终于明白了！这道题的关键就是算出以 i 结尾的子序列最大和的最大值。
- A B C D E F G(每个字母代表一个数字)
- max(A) -> A自己
- max(B) -> 以A结尾的最大和子序列+B自己或者是B自己 ->
max(max(A) + B, B)->if (A > B) return A else return B - max(C) -> max(max(B) + C, C)
- …
- max(G) -> max(max(F) + G, G)
然后 max(A) … max(G) 哪个最大就是哪个了。
算出来以0结尾的最大和子序列 ...
算出来以length-1结尾的最大和子序列
就覆盖了所有的可能，遍历从0到length-1的最大值就可以了。