题目陈述

题目大意：给定一个有正数有负数的数组，求解连续的一段的元素的和的最大值

算法1：暴力做法

算法思路

  • 枚举左右端点，然后计算这个区间的总和now，跟ans比较，如果比ans大，则更新ans，最后循环结束返回ans

  • 时间复杂度，空间复杂度

    代码实现

    class Solution
{
public:
  int FindGreatestSumOfSubArray(vector<int> array)
  {
      int ans = INT_MIN;
      int len = array.size();
      for (int i = 0; i < len; i++)//枚举左端点
      {
          for (int j = i; j < len; j++)//枚举右端
          {
              int now = 0;
              for (int k = i; k <= j; k++)//计算区间和
              {
                  now += array[k];
              }
              ans = max(now, ans);//更新ans
          }
      }
      return ans;
  }
};

    算法2：前缀和优化

    算法思路

  • 我们发现上面的过程中，会重复计算很多的子区间的总和，所以我们用前缀和优化，

  • 第一个数到第j个数的和，减去第一个数到第i-1个数的和，即得到第i个数到第j个数的和，即

  • 时间复杂度，空间复杂度（因为定义了一个sum数组）

    代码实现

    class Solution{
public:
  int FindGreatestSumOfSubArray(vector<int> array)
  {

      int ans=INT_MIN;
      int len = array.size();
      vector<int> sum(len+1,0);
      //sum[0]设为空集，
      //sum[i+1]设为array[0,i]的和，其中i=0~len-1
      //约定array[-1]==0为空集
      for(int i=0;i<len;i++){
          sum[i+1]=sum[i]+array[i];//计算前缀和
      }

      for (int i = 0; i < len; i++)//约定array[-1]==0为空集
      {
          for (int j = i+1; j <= len; j++)
          {
              ans=max(ans,sum[j]-sum[i]);//计算[i-1,j-1]的和
          }
      }
      return ans;
  };
};

    算法3：动态规划

    算法思路

  • 设dp[n]为以第n个数为结尾，得到的子数组的和的最大值

  • 因为以第n个数为结尾所以array[n]是必然被选择的

  • 基于dp[n-1]的值，如果dp[n-1]>0，我们加上这个正数，我们的值是不是必然会增大

  • 如果dp[n-1]<0,那么我们加上负数，我们的值就会减小，这个时候我们不如不要前面的结果，只要当前这个数，结果反而更优

  • 于是我们就得到了状态转移方程dp[n]=array[n]+(dp[n-1]>0?dp[n-1]:0)，实时跟ans比较，更新最大值即可

  • 时间复杂度，空间复杂度（定义了一个dp数组）

    优化算法（空间复杂度）

  • 我们可以发现当前状态只跟上一个状态有关，所以我们可以只用一个int来代替dp数组，即num

  • 如果num<0，那么这个时候就num=array[i]

  • 如果num>0，那么就num=num+array[i]

  • 然后实时跟ans比较，更新最大值即可

  • 时间复杂度，空间复杂度

    动画演示

    图片说明

    代码实现

    C++

    class Solution
{
public:
  int FindGreatestSumOfSubArray(vector<int> array)
  {
      int now, ans;
      now = 0, ans = INT_MIN;
      for (int i = 0; i < array.size(); i++)
      {
          if (now < 0)//now<0,则舍去前面的
              now = array[i];
          else
          {
              now += array[i];//比0大则直接加上去
          }
          ans = max(now, ans);//更新ans
      }
      return ans;
  }
};

    python

    class Solution:
  def FindGreatestSumOfSubArray(self, array):
      now=0
      ans=-1000000000
      for i in array:#此处i即代表array里面的第i个元素的值
          if now<0 :
              now=i#now<0,则舍去前面的
          else :
              now+=i
          ans=max(ans,now)#更新ans
      return ans