JS股票

时间:2022-09-28 夏安人气:2

1. 最佳买卖股票时机含冷冻期

题目描述

给定一个整数数组prices，其中第prices[i]表示第i天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]
输出: 0

力扣链接

题解

我们用 dp[i] 表示第 i 天结束之后的「累计最大收益」。根据题目描述，由于我们最多只能同时买入（持有）一支股票，并且卖出股票后有冷冻期的限制，因此我们会有三种不同的状态：

我们目前持有一支股票，对应的累计最大收益记为 dp[i][0]；
我们目前不持有任何股票，并且处于冷冻期中，对应的累计最大收益记为 f[i][1]；
我们目前不持有任何股票，并且不处于冷冻期中，对应的累计最大收益记为 f[i][2]。

如何进行状态转移呢？在第 i 天时，我们可以在不违反规则的前提下进行买入或者卖出操作，此时第 i 天的状态会从第 i−1 天的状态转移而来；我们也可以不进行任何操作，此时第 i 天的状态就等同于第 i−1 天的状态。那么我们分别对这三种状态进行分析：

对于 dp[i][0]，我们目前持有的这一支股票可以是在第 i−1 天就已经持有的，对应的状态为 f[i−1][0]；或者是第 i 天买入的，那么第 i-1 天就不能持有股票并且不处于冷冻期中，对应的状态为 dp[i−1][2] 加上买入股票的负收益 prices[i]。因此状态转移方程为：dp[i][0]=max(dp[i−1][0], dp[i−1][2]−prices[i])

对于 dp[i][1]，我们在第 i 天结束之后处于冷冻期的原因是在当天卖出了股票，那么说明在第 i−1 天时我们必须持有一支股票，对应的状态为 dp[i−1][0] 加上卖出股票的正收益 prices[i]。因此状态转移方程为：dp[i][1]=dp[i−1][0]+prices[i]

对于 dp[i][2]，我们在第 i 天结束之后不持有任何股票并且不处于冷冻期，说明当天没有进行任何操作，即第 i-1 天时不持有任何股票：如果处于冷冻期，对应的状态为 dp[i−1][1]；如果不处于冷冻期，对应的状态为 dp[i−1][2]。因此状态转移方程为：dp[i][2]=max(dp[i−1][1],dp[i−1][2])

这样我们就得到了所有的状态转移方程。如果一共有 n 天，那么最终的答案即为：max(dp[n−1][0],dp[n−1][1],dp[n−1][2])

注意到如果在最后一天（第 n−1 天）结束之后，手上仍然持有股票，那么显然是没有任何意义的。因此更加精确地，最终的答案实际上是 dp[n-1][1] 和 dp[n-1][2] 中的较大值，即：max(dp[n−1][1],dp[n−1][2])

注意到上面的状态转移方程中，dp[i][..] 只与 dp[i-1][..] 有关，而与 dp[i-2][..] 及之前的所有状态都无关，因此我们不必存储这些无关的状态。也就是说，我们只需要将 dp[i-1][0]，dp[i−1][1]，dp[i-1][2] 存放在三个变量中，通过它们计算出 dp[i][0]，dp[i][1]，dp[i][2] 并存回对应的变量，以便于第 i+1 天的状态转移即可。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  const length = prices.length;
  let [dp0, dp1, dp2] = [-prices[0], 0, 0];
  for(let i = 1; i < length; i++) {
    let newDp0 = Math.max(dp0, dp1 - prices[i]);
    let newDp1 = Math.max(dp1, dp2);
    let newDp2 = dp0 + prices[i];
    dp0 = newDp0;
    dp1 = newDp1;
    dp2 = newDp2;
  }
  return Math.max(dp1, dp2);
};

2. 买卖股票的最佳时机 III

题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

输入：prices = [1]
输出：0

力扣链接

题解

每一天结束之后，有可能处于以下五种状态之一：

没有买股也没有卖股。
买了第一支股，但是还没有卖出第一支股。
买了第一支股，并且卖出第一支股。
买了第一支股，并且卖出第一支股，买了第二支股，但是还没有卖出第二支股。
买了第一支股，并且卖出第一支股，买了第二支股，并且卖出第二支股。

我们可以遍历 prices 数组，模拟第 i 天的情况。计算出第 i 天五种情况利润的最大值。

对于第一种情况，利润始终为 0。
对于第二种情况，由于还没有盈利，只买进了某支股，为亏损状态。此时，亏损的最小值是 prices[0] 至 prices[i] 的最小值，假设为 buy1。可以看做，第二种情况利润的最大值为：-buy1。状态转移方程为：buy1 = max(buy1, -prices[i]);
对于第三种情况，利润的计算需要在第二种情况的基础上再卖出一支股。所以需要先计算第二种情况，再在遍历到 prices[i] 的时候，判断要不要卖出。如果在以最小的亏损买入第一支股的情况下，卖出当前这支股所得利润最大，则卖出当前这支股。状态转移方程为：sell1 = max(sell1, prices[i] + buy1); 注意这里是 prices[i] + buy1，不是 prices[i] - buy1，因为 buy1 是负值，代表利润。
对于第四种情况，不能直接买入，因为有可能第一支股还没卖出。利润的计算需要在第三种情况的基础上再买入一支股。所以需要先计算第三种情况，再在遍历到 prices[i] 的时候，判断要不要买入。如果在卖出第一支股所得利润最大的情况下，买入当前这支股最终所得利润最大，则买入当前这支股。状态转移方程为：buy2 = max(buy2, sell1 - prices[i]);
对于第五种情况，利润的计算需要在第四种情况的基础上再卖出一支股。所以需要先计算第四种情况，再在遍历到 prices[i] 的时候，判断要不要卖出。如果在卖出第一支股然后买入第二支股所得利润最大的情况下，卖出当前这支股所得利润最大，则卖出当前这支股。状态转移方程为：sell2 = max(sell2, prices[i] + buy2);

最终的 sell2 就是我们要的答案。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  const n = prices.length;
  let buy1 = -prices[0];
  let sell1 = 0;
  let buy2 = -prices[0];
  let sell2 = 0;
  for (let i = 1; i < n; i++) {
    buy1 = Math.max(buy1, -prices[i]);
    sell1 = Math.max(sell1, prices[i] + buy1);
    buy2 = Math.max(buy2, sell1 - prices[i]);
    sell2 = Math.max(sell2, prices[i] + buy2);
  }
  return sell2;
};

加载全部内容