原创博文，转载请注明出处！
本题牛客网地址
# 题目
输入一个整形数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值，时间复杂度为O(n)。
# 思路
分析计算连续子数组最大和的规律
下图是我们计算数组（1，-2，3，10，-4，7，2，-5）中子数组的最大和的过程。设置两个辅助变量，即累加子数组和cur_sum、最大子数组和max_sum。初始的累加子数组和cur_sum为数组的第一个元素，初始的最大子数组和max_sum为数组的第一个元素。
# 代码
1 class Solution { 2 public: 3 int FindGreatestSumOfSubArray(vector<int> array) 4 { 5 // 鲁棒性 6 if(array.empty())return 0; 7 8 // 辅助变量 9 int cur_sum = array[0];// cur_sum为当前和 10 int max_sum = array[0];// max_sum为最大和 11 12 // 遍历所有元素 13 for(int i = 1; i < array.size(); ++i) 14 { 15 // 更新cur_sum 16 if(cur_sum <= 0){ 17 cur_sum = array[i]; 18 } 19 else{ 20 cur_sum += array[i]; 21 } 22 // 跟新max_sum 23 if(cur_sum > max_sum){ 24 max_sum = cur_sum; 25 } 26 } 27 return max_sum; 28 } 29 };
原文：https://www.cnblogs.com/wanglei5205/p/8824301.html