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

连续子数组的最大和

http://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484

题目陈述

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

算法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 
全部评论
前缀和的方式会超时
点赞 回复 分享
发布于 2023-08-18 13:48 陕西
1
点赞 回复 分享
发布于 2022-01-20 22:58

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司10个岗位
点赞 评论 收藏
分享
06-26 17:24
已编辑
宁波大学 Java
迷失西雅图:别给,纯kpi,别问我为什么知道
点赞 评论 收藏
分享
评论
28
10
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务