原创博文，转载请注明出处！
本题牛客网地址
# 题目
输入一个整形数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值，时间复杂度为O(n)。
# 思路
分析计算连续子数组最大和的规律。下图是我们计算数组（1，-2，3，10，-4，7，2，-5）中子数组的最大和的过程。设置两个辅助变量，累加子数组和cur_sum、最大子数组和max_sum。初始的累加子数组和cur_sum为数组的第一个元素，初始的最大子数组和max_sum为数组的第一个元素。更新cur_sum方法：如果cur_sum>0，则继续累加；否则用下一个元素值替换累加的子数组和。更新max_sum方法：如果cur_sum >max_sum，则用累加的子数组和替换最大的子数组和。
# 代码
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array)
{
// 鲁棒性
if(array.empty())return 0;
// 辅助变量
int cur_sum = array[0];// cur_sum为当前和
int max_sum = array[0];// max_sum为最大和
// 遍历所有元素
for(int i = 1; i < array.size(); ++i)
{
// 更新cur_sum
if(cur_sum <= 0){
cur_sum = array[i];
}
else{
cur_sum += array[i];
}
// 跟新max_sum
if(cur_sum > max_sum){
max_sum = cur_sum;
}
}
return max_sum;
}
};