！
求一段整数中最大子序列和
2.全面讨论此问题的性质，得到o(n)的最优算法
对于原序列a1，a2，a3......an的最优子序列ai, a(i+1)......aj;
将在以序列元素ai作为末端的子序列中，和最大的称作“ai为末端的最优子序列”记做"ai末最优";
将在以序列元素aj作为开始的子序列中，和最大的序列称作”aj为首端的最优子序列"记做"aj首最优";
有如下几条性质：
?????????性质1：?对于任意的k < i, 均有ak + a(k + 1)......a(i-1) <= 0；对于任意m? m > j && m <=n?有 a(j+1), a(j+2).....am <=0。?
?????????性质2：?设m ∈ 最优子区间[i,j], 那么 ai, a(i+1), a(i+2)......am 必然是"am末最优"; 同理, am, a(m+1)......a(j)必然是"am首最优"。
????????? 性质3：任何一个最优子序列，即是它首端元素的ai的"ai首最优", 同时也是其末端元素aj的"aj末最优"。
记"aj末最优"的序列和为sum_e(j), "ai首最优"的序列和为sum_s(i)则有如下递推公式：
?????????? sum_e(j) = aj + max(0, sum_e(j-1));?
????????? sum_s(i) = ai + max(0, sum_s(i+1));
由于最优子序列既是某一序列元素ai的"末最优"，也是某一序列元素的"首最优", 因此，可以用上述两个公式得出两个不同方向扫描的o（n）算法，求得最优子序列和， 以"末最优"为例，代码如下：
原文：https://www.cnblogs.com/liuziwen0224/p/12031413.html