连续子数组的最大和
C++，最大连续子列和，在线处理算法。
非常经典的题目啦，其实用dp也很简单，不过在线处理算法不用额外空间显然更胜一筹。
思路：
- 遍历序列，用变量tsum记录包含当前位置的连续子列和，ans记录序列的最大连续子列和；
- 如果包含当前元素，能让tsum大于ans，则更新ans为tsum；
- 如果包含当前元素，tsum < 0，则说明tsum从下一个位置重新开始累加值会更大，所以tsum = 0；
- 记得特殊情况：序列全为负。
代码：
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
int tsum = 0, ans = 0;
int max_neg = array[0];
for (int &it : array) {
tsum += it;
if (tsum < 0) {
tsum = 0;
}
if (tsum > ans) {
ans = tsum;
}
max_neg = max(it, max_neg);
}
return ans > 0 ? ans : max_neg;
}
};
