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

连续子数组的最大和：最直观的想法是，使用一个变量i枚举区间起始位置，使用一个变量j枚举区间结束位置，使用一个变量k枚举区间变量值用于求和，使用一个变量sum用于求区间和，使用一个变量ans用于求区间和最大值，三层for循环。（但是很明显该方法超时故我们需要优化时间复杂度）

int FindGreatestSumOfSubArray(vector<int> array) {
        //数组长度
        int n=array.size();
        //最大和
        int ans=INT_MIN;
        //起始位置
        for(int i=0;i<n;i++)
        {
            //结束位置
            for(int j=i;j<n;j++)
            {
                int sum=0;
                //区间和
                for(int k=i;k<=j;k++)
                {
                    sum+=array[k];
                }
                ans=max(ans,sum);
            }
        }
        return ans;
    }

优化：上述方法存在一个问题，其重复计算了很多次区间和，我们可以使用前缀和优化，即区间[i,j]的区间和等于区间[0,j]的区间和减去区间[0,i-1]的区间和，故额外使用一个sum数组记录区间和。为了使得代码统一，可以使用sum[i+1]表示0~i区间和，其中sum[0]设为空集，即可统一递推式。（这样可以将三层for循环降为两层for循环但是还是超时故需要继续优化时间复杂度）

  int FindGreatestSumOfSubArray(vector<int> array) {
        //数组长度
        int n=array.size();
        //区间和最大值
        int ans=INT_MIN;
        //前缀和数组 sum[0]设为空集 sum[i+1]表示0~i区间和
        vector<int> sum(n+1,0);
        for(int i=0;i<n;i++)
            sum[i+1]=sum[i]+array[i];
        //起始位置
        for(int i=0;i<n;i++)
        {
            //结束位置
            for(int j=i;j<n;j++)
            {
                ans=max(ans,sum[j+1]-sum[i]);
            }
        }
        return ans;
    }

优化：上述两种方法均是枚举了起始位置和结束位置，但是实际上我们可以只枚举结束位置，不妨使用dp[i]表示以i为结尾的连续子数组的最大值，既然是以i为结尾，那么肯定是要包含i元素的。又由于其需要连续子数组，故如果dp[i-1]小于等于0，那么dp[i]就等于array[i]，反之就等于dp[i-1]加上array[i]。最后使用一个变量res来记录最大值，即以哪一个元素为结尾的连续子数组和最大。

  int FindGreatestSumOfSubArray(vector<int> array) {
        //dp数组
        vector<int> dp(array.size(),0);
        dp[0]=array[0];
        int res=dp[0];
        for(int i=1;i<array.size();i++)
        {
            dp[i]=max(dp[i-1]+array[i],array[i]);
            res=max(res,dp[i]);
        }
        return res;
    }

优化：上述动态规划方法，我们发现每次最多只会使用上一个状态，故我们不需要使用dp数组进行存储，直接使用一个int变量存储即可。

int FindGreatestSumOfSubArray(vector<int> array) 
{
   int sum=array[0];
   int res=array[0];
   for(int i=1;i<array.size();i++)
   {
      sum=max(sum+array[i],array[i]);
      res=max(res,sum);
   }
   return res;
}

PS：最开始刷题一题一解就可以，但是刷多了后可以尝试变换思维，想想一题多解，即最直观的最暴力的想法是什么，然后接着想想有哪些缺点即有哪些优化空间。