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

题目的主要信息：

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

1. 子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
2. 如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个
3. 该题定义的子数组的最小长度为1，不存在为空的子数组，即不存在[]是某个数组的子数组
4. 返回的数组不计入空间复杂度计算

方法一：

动态规划。dp数组为动态数组，dp[i]表示以下标i为终点的最大连续子数组和，遍历一遍动态数组，更新值为dp[i-1]+array[i]和array[i]中较大的那个，并且如果值大于max_sum，还需要更新最大和的值和末位置。遍历一遍动态数组后，max_sum中保存了最大的连续子数组最大和，再从连续子数组末尾开始遍历，找数组的起始位置，然后返回这个连续子数组。

• 动态规划方程为：$dp[i]=max(dp[i-1]+array[i],array[i])dp[i]\; =\; max(dp[i\; -\; 1]\; +\; array[i],array[i])$

具体做法：

class Solution {
public:
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        int n = array.size();
        vector<int> dp(n,0);//动态数组
        dp[0] = array[0];//初始化
        int max_sum = dp[0];
        int end = 0;
        for (int i = 1; i < n; i++){//遍历一遍数组
            dp[i] = max(dp[i - 1] + array[i],array[i]);//更新动态数组
            if (dp[i] >= max_sum){
                end = i;//更新连续子数组的末位置
                max_sum = dp[i];//更新连续子数组的最大和
            }
        }
        int start = 0;
        for (int i = end; i >= 0; i--){//遍历一遍数组找到起始位置
            max_sum -= array[i];
            if (max_sum == 0){
                start = i;
            }
        }
        return vector<int>(array.begin()+start,array.begin()+1+end);//返回连续子数组
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历一遍数组。
• 空间复杂度：$O(n)O(n)$，动态数组dp的大小为n。

方法二：

用动态规划的方法。在动态规划的基础上，增加几个指针pre、start、end。pre保存当前遍历位置子串首位置；start和end保存最大和子串首尾位置。遍历一遍数组，如果当前连续子数组和小于0，则重新开始找连续子数组。根据实际情况判断是否要更新，如果需要更新最大子数组的和，还需要更新数组始末位置的指针。最后，根据start和end返回连续子数组。 具体做法：

class Solution {
public:
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        int n = array.size();
        //初始化各指针
        int pre = 0;
        int start = 0,end=0;
        int max_sum = array[0];
        int temp = array[0];//暂存已知的连续子数组的最大和
        if(n==0){//如果数组为空，也返回一个空数组
            return array;
        }
        for(int i = 1; i<n; ++i){//遍历一遍数组
            if(temp < 0){//如果连续子数组和小于0，重新开始找
                temp=0;
                pre = i;
            }
            temp += array[i];//计算pre到i这个子数组的和
            if(temp >= max_sum){//更新最大和的值
                max_sum = temp;
                start = pre;//起始
                end = i;//终点
            }
        }
        return vector<int>(array.begin()+start,array.begin()+end+1);
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历一遍数组。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。