最大和连续子序列问题

我们令F(n)表示[0,n]区间内以d[n]为结尾的最大和，d为原序列，那么有： F(n + 1) = Max{d[n + 1],F(n) + d[n + 1]} = d[n + 1] + Max{0, F(n)} 为什么不用考虑F(n-1) + d[n ]+d[n+1 ] 的情况呢？ F(n-1) + d[n ]+d[n+1 ] F(n) + d[n + 1] 消掉d[n+1]后实质上是比较 F(n-1) + d[n ] F(n) 的大小 又因为F(n)={d[n],F(n-1) + d[n ]} 所以在考虑F(n)时，已经考虑过以前的了，若以前的较大则F(n)会选择较大的，所以F(n)一定为最优的。