Heara.in

Leetcode股票问题

2020 M04 20 • ☕️ 2 分钟阅读

最近刷Leetcode发现了一个股票问题系列,总结一下

第一题 上手

121. Best Time to Buy and Sell Stock

一个典型的动态规划问题,我们需要解决的问题是找到一个连续子序列,这个子序列首位差值最大。 定义dp[i]是以第i天卖出的最大收益,price[i]为第i天股票价格,则有:

dp[i] = Math.max(0, dp[i - 1] + (price[i] - price[i - 1]))
/**
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = function (prices) {
  if (prices.length <= 1) {
    return 0;
  }
  const dp = Array.from({ length: prices.length }).fill(0);
  dp[0] = 0;
  let max = 0
  for (let index = 1; index < dp.length; index++) {
    const prev = prices[index - 1];
    const current = prices[index];
    const diff = (current -prev);
    dp[index] = Math.max(0, dp[index - 1] + diff);
    max = Math.max(dp[index], max)
  }
  return max
};

第二题 继续

122. Best Time to Buy and Sell Stock II

这一题与上一题的主要区别是可以多次买入卖出,但是买入前必须卖出

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  if (prices.length <= 1) {
    return 0;
  }
  // hold[i]表示第[i]天手里没有股票
  // sold[i]表示第[i]天手里没有股票
  const hold = Array.from({ length: prices.length });
  const sold = Array.from({ length: prices.length });
  hold[0] = -prices[0];
  sold[0] = 0;
  for (let i = 1; i < prices.length; i++) {
    // 第i天有股票 可能是【i-1天有股票】 或者【 i-1没有股票第i天买入】
    hold[i] = Math.max(hold[i - 1], sold[i - 1] - prices[i]);
     // 第i天没有股票 可能是【i-1天没有股票】 或者【 i-1有股票第i天卖出】
    sold[i] = Math.max(sold[i - 1], hold[i - 1] + prices[i]);
  }
  return sold[prices.length - 1];
};