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

连续子数组的最大和(二)：最直观的想法是，相对于(一)其区别在于要记录区间起始位置和结束位置，并且相同最大和的情况下返回长度最长的数组，而(一)中我们使用的是dp[i]表示以下标i为结尾的连续子数组的最大和，其递推公式为dp[i]= max(dp[i-1]+array[i],array[i])。那么怎么办呢？我们可以使用start和end分别表示当前区间起始位置和结束位置，初始均为0，maxs和maxe分别表示最大和区间起始位置和结束位置，初始也均为0，dp[0]初始化为第一个元素值，使用maxres表示最大和，初始为第一个元素值。与(一)的区别在于，每次循环遍历i时记录结束位置end为i，使用公式更新完dp[i]后，如果dp[i-1]+array[i]小于array[i]，那么就更新起始位置为i，同时当dp[i]大于maxres或者dp[i]等于maxres且区间长度更大时，则更新最长区间以及最大值。最后将[maxs,maxe]区间的数值加入到结果数组中即可。

vector<int> FindGreatestSumOfSubArray(vector<int>& array) 
{
    int n=array.size();
    // dp[i]表示已i为结尾的连续子数组 dp[i]=max(dp[i-1]+array[i],array[i])
    vector<int> dp(n,0);
    // 此处要求有多个的话返回最长的 故要记录起始和结束
    int start=0,end=0; //最初区间为第一个元素
    dp[0]=array[0];
    int maxres=array[0]; //记录最大区间和为第一个元素
    int maxs=0,maxe=0; //最初区间为第一个元素
    for(int i=1;i<n;i++)
    {
       end=i; //结束位置为i
       dp[i]=max(dp[i-1]+array[i],array[i]);
       // 更新起始位置
       if(dp[i-1]+array[i]<array[i])
          start=i;
       // 更新最长区间以及最大值
       if(dp[i]>maxres||(dp[i]==maxres && end-start+1 > maxe-maxs+1))
       {
          maxe=end;
          maxs=start;
          maxres=dp[i];
       }
    }
    vector<int> res;
    for(int i=maxs;i<=maxe;i++)
       res.push_back(array[i]);
    return res;
}