题解 | #连续子数组的最大和#

连续子数组的最大和

1、题意重述

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

换句话说，就是求和最大的子数组。

2、思路整理

使用贪心的思想：

Step1:用cur表示当前子数组的和，array[i]表示可能会加入子数组的数。

Step2：如果cur + array[i] > 0，用贪心的思想，说明目前这个子数组还有可能会继续增加，因此我们保留这个子数组并加上当前值，继续i++。

Step3：重复Step2,保留最大值，返回结果即可。

3、代码实现

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int n = array.size();
        int ans = INT_MIN, cur = 0;
        for(int i = 0; i < n; i++){
            cur += array[i];    // 尝试加上当前数
            ans = max(ans, cur);    // 更新
            if(cur < 0) cur = 0;    // 如果小于0，则重置子数组
        }
        return ans;    // 返回结果
    }
};

4、复杂度分析

时间复杂度：一层循环，因此时间复杂度为$O(N)O(N)$。

空间复杂度：使用了常数级内存地址空间，因此空间复杂度为$O(1)O(1)$。