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

共以下 14 个回答

• 招舟子 普通 2023年12月6日 下午3:03

  class Solution {
  public int bestTiming(int[] prices) {
  if(pricesnull||prices.length0){
  return 0;
  }
  int[][] dp = new int[prices.length][2];
  dp[0][0] = 0;
  dp[0][1] = -prices[0];
  for(int i=1;i<prices.length;i++){
  dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
  dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
  }
  return dp[prices.length-1][0];
  }
  }
  动态规划

  0 赞同 0 条回复

  登录以回复
• 九号球 普通 2023年12月2日 下午10:28

  “`java
  class Solution {
  public int bestTiming(int[] prices) {
  //dp[i]表示第i天卖出的最大利润，则dp[i] = max(0, dp[i – 1] + prices[i] – prices[i – 1])
  int length = prices.length;
  if (length <= 1) { return 0; } if (length == 2) { return Math.max(0, prices[1] - prices[0]); } int[] dp = new int[length]; dp[0] = 0; int max = 0; for (int i = 1; i < length; i++) { dp[i] = Math.max(0, dp[i - 1] + prices[i] - prices[i - 1]); max = Math.max(dp[i], max); } return max; } }

  0 赞同 0 条回复

  登录以回复
• 张开怀 普通 2023年7月24日 下午12:44

  class Solution {
  public:
      int maxProfit(vector<int>& prices) {
          int minPrice = INT_MAX;
          int maxProfit = 0;
          for (int price : prices) {
              if (price < minPrice) {
                  minPrice = price;
              } else {
                  maxProfit = max(maxProfit, price - minPrice);
              }
          }
          return maxProfit;
      }
  };
  

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

  0 赞同 0 条回复

  登录以回复
• Dsjh 普通 2023年7月23日 上午12:32

  #MY

  // 维护最小价格
  class Solution {
  public:
      int maxProfit(vector<int>& prices) {
          if(prices.size()==0){
              return 0;
          }
          int ans=0,minprice=prices[0];
          for(int i=1;i<prices.size();i++){
              ans = max(ans,prices[i]-minprice);
              minprice = min(minprice,prices[i]);
          }
          return ans;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 哈哈哈哈开开心心 普通 2023年7月23日 上午12:23

  class Solution:
      def maxProfit(self, prices: List[int]) -> int:
          dp = [[0] * 2 for _ in range(len(prices))]
  
          dp[0][0] = - prices[0]
  
          for i in range(1, len(prices)):
              dp[i][0] = max(dp[i - 1][0], -prices[i])
              dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
  
          return max(dp[len(prices) - 1][0], dp[len(prices) - 1][1])
  

  动态规划

  0 赞同 0 条回复

  登录以回复
• BOZ 普通 2023年7月22日 上午10:46

  【思路】DP思路，在第i天卖掉股票的最大收益为prices[i]-minprice，后者为0…i天中股票最低价，因此需要一个min变量记录股票最低价
  【复杂度】时间O(n)，空间(1)

  class Solution {
  public:
      int maxProfit(vector<int>& prices) {
          if (prices.size() <= 1) return 0;
  
          // dp[i] is the max profit to sell the stock on day[i]
          int max = 0;
          int low = prices[0];
          for(int i = 1; i < prices.size(); i++) {
              low = std::min(low, prices[i]);
              max = std::max(max, prices[i] - low);
          }
  
          return max;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 花老爷 普通 2023年7月21日 下午12:38

  动态规划，找出该元素前的最小值即可
  时间：O(n)
  空间：O(1)

  class Solution {
      public int maxProfit(int[] prices) {
          int ans = 0, min = Integer.MAX_VALUE;
          for (int price: prices) {
              min = Math.min(min, price);
              ans = Math.max(ans, price - min);
          }
          return ans;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 局外人 普通 2023年7月20日 下午6:01

  思路：动态规划，根据休息、买、卖三种状态进行转移
  时间复杂度：O(n) 空间复杂度：O(n)

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

  0 赞同 0 条回复

  登录以回复
• Ming 普通 2023年7月20日 下午4:29

  设置最小值买入价格，设置最大利润，一旦当前值大于买入就试着卖一下比较最大值

      public int maxProfit(int[] prices) {
          int max = 0;
          int min = Integer.MAX_VALUE;
          for(int i = 0; i < prices.length; i++) {
              if(prices[i] < min) {
                  min = prices[i];
              } else {
                  max = Math.max(max, prices[i] - min);
              }
          }
          return max;
      }
  

  0 赞同 0 条回复

  登录以回复
• 怀瑾 永久会员 2023年7月20日 上午8:37

  C++实现

  “`C++
  int maxProfit(vector& prices) {
  int minPrice = prices[0];
  int maxProfit = 0;

  for (int i = 1; i < prices.size(); ++i) {
      int profit = prices[i] - minPrice;
      maxProfit = std::max(maxProfit, profit);
      minPrice = std::min(minPrice, prices[i]);
  }
  
  return maxProfit;
  

  }

  “`

  0 赞同 0 条回复

  登录以回复
• mpweixin用户 永久会员 2023年7月19日 上午12:56

  class Solution {
      public int maxProfit(int[] prices) {
          if(prices.length == 0 || prices.length == 1){
              return 0;
          }
          int dp = prices[1] - prices[0] > 0 ? prices[1] - prices[0] : 0; //  第i天卖出的利润
          int max = dp;
  
          for(int i = 2;i < prices.length;i++){
  
              dp = dp + (prices[i] - prices[i - 1]);
              if(dp < 0){//倒贴钱
                  dp = 0;//不卖，即当天利润为0
              }
              if(dp > max){
                  max = dp;
              }
  
          }
          return max;
      }
  

  0 赞同 0 条回复

  登录以回复
• 小吕 普通 2023年7月18日 下午9:28

  c++实现
  int maxProfit(vector& prices) {
  int min_price = INT_MAX;
  int max_profit = 0;
  for(auto num:prices)
  {
  if(num<min_price)
  {
  min_price = num;
  }
  else
  {
  max_profit= max(max_profit,num-min_price);
  }
  }
  return max_profit;
  }

  0 赞同 0 条回复

  登录以回复
• yxy 普通 2023年7月18日 下午4:46

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

  class Solution {
  public:
      int maxProfit(vector& prices) {
          int prev = 0, cur = 0;
          int res = 0;
          for(int i=1;i0)
                  cur = prev+prices[i]-prices[i-1];
              else
                  cur = 0;
              res=max(res, cur);
              prev = cur;
          }
          return res;
      }
  };
  

  以下是空间复杂度为O(n)的dp

  class Solution {
  public:
      int maxProfit(vector& prices) {
          vector dp(prices.size(), 0);
          int res = 0;
          for(int i=1;i

  怎么把我代码吞了？

  0 赞同 0 条回复

  登录以回复
• Yodl. 普通 2023年7月18日 下午2:01

  //时间复杂度O(n) 空间复杂度O(n) 
  class Solution {
  public:
      int maxProfit(vector<int>& prices) {
          if(prices.size()==0)
          {
              return 0;
          }
          int dp[prices.size()];
          int min=prices[0];
          dp[0]=0;
          for(int i=1;i<prices.size();i++)
          {
              dp[i]=max(dp[i-1],prices[i]-min);//dp[i]=max(dp[i-1],prices[i]-min);
              if(min>prices[i])
              {
                  min=prices[i];
              }
          }
          return dp[prices.size()-1];
      }
  };
  

  0 赞同 0 条回复

  登录以回复