【动态规划专题】剑指 Offer 63. 股票的最大利润

共以下 3 个回答

• JustRtn 普通 2023年9月18日 下午3:17

  class Solution {
  public:
      int maxProfit(vector<int>& prices) {
          int maxVal = 0;
          int minVal = INT_MAX;
          for (auto& a : prices) {
              if (a < minVal) {
                  minVal = a;
              } else {
                  maxVal = max(maxVal, a - minVal); // 当前价格减去历史最小值
              }
          }
          return maxVal;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 别扒拉我 普通 2023年9月14日 上午12:17

  定义一个变量存储i前面的最小值

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

  0 赞同 0 条回复

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

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

  class Solution {
      public int maxProfit(int[] prices) {
          //特殊情况
          if (prices.length == 0){
              return 0;
          }
  
          int min = Integer.MAX_VALUE;
          int max = 0;
  
          for (int i = 0; i < prices.length; i++) {
              if (prices[i] < min) {
                  min = prices[i];
              } else {
                  max = Math.max(max, prices[i] - min);//递推式：历史低价买入当前卖出与之前的最大收益相比
              }
          }
  
      }
  }
  

  0 赞同 0 条回复

  登录以回复