输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

 

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        /*此处的代码是因为题目给出了提示，1 <= arr.length <= 10^5，即nums数组大小的范围
        if (nums.size() == 1) {
			return nums[0];
		}
        */
        //如果数组的大小为0，直接返回0即可
        if (nums.size() == 0) {
			return 0;
		}
		int sum = 0;
		int max = INT_MIN;//由于我们求的是最大值，所以给max初始值赋为INT_MIN
        //遍历整个nums数组，用sum记录当前子数组的和
		for (int i = 0; i < nums.size(); i++) {
			sum += nums[i];
            //如果sum比max大，则更新max的值
			if (sum > max) {
				max = sum;
			}
            //由于sum记录的是当前子数组的和，如果<0，直接将sum赋为0，因为如果sum<0，不论下一个待遍历的数是正数还是负数，都影响我求所有子数组的和的最大值
			if (sum < 0) {
				sum = 0;
			}
		}
		return max;
    }
};