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

共以下 7 个回答

• 陆狗陆狗 普通 2024年12月25日 上午9:58

  解题思路
  – dp[n]的含义，以sales[n]结尾的连输子数组最大和(难点在于这个定义，之前自己定义的数组长度为n的最大和)
  – dp[n]= dp[n-1]<0，那么dp[n]=sales[n];dp[n-1]>0，那么dp[n]=dp[n-1]+sales[n]
  – 最后我们只需要在所有dp里面取出最大值即可
  【题解1】使用一维数组dp进行解答

  class Solution {
      public int maxSales(int[] sales) {
          // dp[n]的含义，以sales[n]结尾的连输子数组最大和(难点在于这个定义，之前自己定义的数组长度为n的最大和)
          // dp[n]= dp[n-1]<0，那么dp[n]=sales[n]
          // dp[n-1]>0，那么dp[n]=dp[n-1]+sales[n]
          // 最后我们只需要在所有dp里面取出最大值即可
          int[] dp = new int[sales.length];
          dp[0] = sales[0];
          int max = sales[0];
          for (int i = 1; i < sales.length; i++) {
              dp[i] = dp[i - 1] > 0 ? dp[i - 1] + sales[i] : sales[i];
              max=Math.max(max,dp[i]);
          }
          return max;
      }
  }
  

  【题解2】把一维数组优化成一个变量

  class Solution {
      public int maxSales(int[] sales) {
          // dp[n]的含义，以sales[n]结尾的连输子数组最大和(难点在于这个定义，之前自己定义的数组长度为n的最大和)
          // dp[n]= dp[n-1]<0，那么dp[n]=sales[n]
          // dp[n-1]>0，那么dp[n]=dp[n-1]+sales[n]
          // 最后我们只需要在所有dp里面取出最大值即可
          int pre = sales[0];
          int max = sales[0];
          for (int i = 1; i < sales.length; i++) {
              pre = pre > 0 ? pre + sales[i] : sales[i];
              max = Math.max(max, pre);
          }
          return max;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 晓宇 普通 2024年12月22日 下午8:38

  class Solution {
  public:
      int maxSales(vector<int>& sales) {
          // dp[i] 以第i天销售额为结尾，连续若干天的最大销售总额
          int las_sum = sales[0];
          int max_val = sales[0];
          for(int i = 1;i < sales.size(); i++){
              las_sum = max(las_sum + sales[i],sales[i]);
              max_val = max(max_val,las_sum);
          }
          return max_val;
      }
      // o(n) o(1)
  };
  

  0 赞同 0 条回复

  登录以回复
• 秋山丽奈 普通 2024年12月22日 下午4:09

  思路： 第i天利润取决于i-1是否亏损

  class Solution {
      public int maxSales(int[] sales) {
          int[] dp = new int[sales.length];
          dp[0] = sales[0];
  
          int max = Integer.MIN_VALUE;
          max = Math.max(dp[0], max);
          for(int i = 1; i < sales.length; i ++){
              if(dp[i-1]<0){
                  dp[i] = sales[i];
              }else{
                  dp[i] = dp[i-1]+sales[i];
              }
              max = Math.max(dp[i], max);
          }
  
          return max;        
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 苯庸 普通 2024年12月21日 下午8:06

  class Solution {
  public int maxSales(int[] sales) {
  int[] dp = new int[sales.length];
  int res = sales[0];
  dp[0] = sales[0];
  for(int i = 1; i < sales.length; i++){
  dp[i] = Math.max(sales[i], dp[i-1] + sales[i]);
  res = Math.max(res, dp[i]);
  }
  return res;
  }
  }
  时间：O（n）
  空间：O（n）

  0 赞同 0 条回复

  登录以回复
• Kisara 普通 2024年12月20日 下午6:46

  优化前：

  class Solution {
      public int maxSales(int[] sales) {
          int[] dp=new int[sales.length];
          dp[0]=sales[0];
          int max=dp[0];
          for(int i=1;imax) max=dp[i];
          }
          return max;
      }
  }
  
  On ON
  优化后
  class Solution {
      public int maxSales(int[] sales) {
          int res=0;
          res=sales[0];
          int max=res;
          for(int i=1;imax) max=res;
          }
          return max;
      }
  }
  

  On O1

  0 赞同 0 条回复

  登录以回复
• Aatorx 永久会员 2024年12月20日 下午3:28

  class Solution {
  public:
      int maxSales(vector<int>& sales) {
          int res = sales[0];
          for(int i = 1; i < sales.size(); i++) {
              if(sales[i - 1] > 0) {
                  sales[i] = sales[i - 1] + sales[i];
              }
              res = max(res, sales[i]);
          }
          return res;
      }
  };
  

  时间复杂度O(N)，空间复杂度O(1)。

  0 赞同 0 条回复

  登录以回复
• 月下足迹 普通 2024年12月20日 上午11:02

  //动态规划
  class Solution {
  public int maxSales(int[] sales) {
  int n = sales.length;
  int [] dp = new int [n];
  dp[0] = sales[0];
  int max = dp[0];
  for (int i = 1; i < n; i++) {
  dp[i] = Math.max(sales[i], sales[i] + dp[i – 1]);
  max = Math.max(max, dp[i]);
  }
  return max;
  }
  }

  0 赞同 0 条回复

  登录以回复