【动态规划专题】剑指 Offer 42. 连续子数组的最大和

共以下 5 个回答

• JustRtn 普通 2023年9月18日 下午12:51

  class Solution {
  public:
      int maxSubArray(vector<int>& nums) {
          int tmp = nums[0];
          int maxVal = tmp;
          for(int i = 1; i < nums.size(); i++) {
              tmp = max(nums[i], nums[i] + tmp); // 之前的值没有贡献时刷新
              maxVal = max(tmp, maxVal);
          }
          return maxVal;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 小肸 永久会员 2023年9月17日 下午2:27

  class Solution {
      public int maxSubArray(int[] nums) {
          int[] dp = new int[nums.length + 1];
          int res = nums[0];
          for (int i = 0; i < nums.length; i ++) {
              //根据上一个元素的最大子数组是否大于等于0判断是否需要累计
              if (dp[i] < 0) {
                  dp[i + 1] = nums[i];
              } else {
                  dp[i + 1] = nums[i] + dp[i];
              }
              res = Math.max(res, dp[i + 1]);
          }
          return res;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 别扒拉我 普通 2023年9月12日 下午2:32

  动态规划
  一、状态定义：dp[i]表示以nums[i]结尾的连续子数组的最大和
  二、转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i]);
  三、初始状态：dp[0]=nums[0]

  class Solution {
      public int maxSubArray(int[] nums) {
          int[] dp = new int[nums.length];
          dp[0] = nums[0];
          int max = dp[0];
          for(int i=1; i<nums.length; i++){
              dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
              max = Math.max(max, dp[i]);
          }
          return max;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• c 普通 2023年9月10日 下午11:17

  动态规划

  class Solution {
      public int maxSubArray(int[] nums) {
          int[] dp = new int[nums.length];
          dp[0]=nums[0];
          int max = nums[0];
          for(int i = 1;i<nums.length;i++){
              dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
              if(dp[i]>max){
                  max=dp[i];
              }
          }
          return max;
  
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 塔底的仰望 永久会员 2023年9月10日 下午3:23

  空间复杂度O(1); 时间复杂度O(n)

  class Solution {
      public int maxSubArray(int[] nums) {
          if(nums.length == 1) {
              return nums[0];
          }
          //dp[i]定义为以第i个元素为末尾的子数组和的最大值。
          int dp = nums[0];
          int max = dp;//记录最大值
          for (int i = 1; i < nums.length; i++) {
              dp = Math.max(dp + nums[i], nums[i]);
              max = max > dp ? max : dp;
          }
  
          return max;
      }
  }
  

  0 赞同 0 条回复

  登录以回复