121. 买股票的最佳时机

[arshelia]

题目链接

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

解题思路

1.动态规划

[arshelia]

var maxProfit = function(prices) {
  let n = prices.length;
  if(n<=0) return 0;
  let dp = new Array(n);
  for(let i = 0; i < n; i++){
    dp[i] = new Array(2);
    if(i - 1 == -1){
      dp[i][0] = 0;
      dp[i][1] = -prices[i];
      continue
    }
    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];
};

[arshelia]

只用一个变量存储

var maxProfit = function(prices){
  let n = prices.length;
  let dp_i_0 = 0, dp_i_1 = -Infinity;
  for (let i = 0; i < n; i++) {
      // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
      dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
      // dp[i][1] = max(dp[i-1][1], -prices[i])
      dp_i_1 = Math.max(dp_i_1, -prices[i]);
  }
  return dp_i_0;
}