一、题目描述

JZ30 连续子数组的最大和
题目大意：输入一个整型数组,数组里有正数也有负数.数组中的一个或连续多个整数组成一个子数组.求所有子数组的和的最大值.要求时间复杂度为 O(n).
注意审题：要求时间复杂度为O(n)

二、算法1（前缀和）

解题思路

1. 连续子数组问题可以联想到区间, 连续子数组的和就是区间和, 区间和就顺其自然地想到的前缀和这个知识点
2. 前缀和的核心是前缀和数组sum, 其中sum[i]表示array[0...i]的和, 显然, 要求区间array[j...i]的和, 实际上就是 sum[i] - sum[j - 1], 用到了集合运算的思想
3. 要求连续子数组的最大和, 我们可以在遍历前缀和数组的同时维护前缀和的最小值minval, 则ans = max(ans, sum[i] - minval)
4. 实现细节, 一般为了实现方便, 我们喜欢让前缀和下标从1开始, 下标0的位置用来存储0, 这样可以避免很多边界问题, 因此我们把数组看做从1开始来构建前缀和数组

代码实现（C++11）

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int n = array.size();
        vector<int> sum(n + 1);
        sum[0] = 0;    
        for(int i = 0; i < n; i++){    // 构建前缀和数组
            sum[i + 1] = sum[i] + array[i];
        }
        int ans = INT_MIN;
        int minval = 0;    // 初始值minval = sum[0]
        for(int i = 1; i <= n; i++){
            ans = max(ans, sum[i] - minval);    // 计算最大值
            minval = min(minval, sum[i]);    // 更新最小值
        }
        return ans;
    }
};

时间复杂度：O(n), 遍历了两次数组
空间复杂度：O(n), 前缀和数组的大小

三、算法2（动态规划）

1. 采用动态规划的方法, 我们定义数组f, f[i]表示以i结尾的子数组的最大和, 计算状态f[i]时, 要么只选i这一个元素, 要么和f[i - 1]结合, 取其中的最大值即可
2. 注意：根据状态数组的定义, 最终答案不一定是f[n], 因此, 我们每次计算完f[i]之后就需要更新一下最优答案
3. 状态转移方程为：
   

代码实现（C++11）

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int n = array.size();
        vector<int> f(n);    // 定义f数组
        f[0] = array[0];    // 边界
        int ans = f[0];    // 初始答案
        for(int i = 1; i < n; i++){
            f[i] = max(array[i], f[i - 1] + array[i]);    // 计算状态
            ans = max(ans, f[i]);    // 更新答案
        }
        return ans;
    }
};

时间复杂度：O(n), 遍历一次数组即可
空间复杂度：O(n), f数组使用的空间

四、算法3（贪心）

1. 本题有一个十分优秀的在线做法, 其思想是基于贪心的: 只要当前的子数组和不小于0, 那么就还有变大的可能
2. 算法实现：用cur变量保存当前子数组的和, 依次加上后续的值, 若cur + next < 0, 则表示加入下一个数一定不会让结果变得更好, 因此从下一个数的下一个重新开始计算, 即令cur = 0, 在更新cur的同时记录答案, 即可得到最大和

代码实现（C++11）

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;    // 检查是否重新考虑
        }
        return ans;
    }
};

时间复杂度：O(n)，n为数组长度，遍历一次数组时间复杂度为O(n)
空间复杂度：O(1) ，定义了常数个变量