seo咨询师招聘_大连金州高级中学_优化大师最新版本_怎样做企业宣传推广

一、问题描述

我们要解决的是一个关于股票买卖的问题：给定一个股票价格数组 stocks，每一天的价格为数组中的一个元素。我们可以通过买入和卖出的操作来获取收益，但需要遵守以下规则：

1. 每次买入前，必须先卖出之前的股票（即不能同时持有两次未卖出的股票）。
2. 卖出股票后有一个冷冻期，也就是说，在卖出后的第二天才能继续买入股票。

我们的目标是：计算出在满足上述规则的情况下，最大可以获得的利润。

例如，给定数组 [1, 2, 3, 0, 2]：

• 第一天买入，花费 -1；
• 第二天卖出，收入 +2；
• 第四天再次买入，花费 -0；
• 第五天卖出，收入 +2。 总收益为 3。

---

二、解决思路

这是一个经典的 动态规划 问题。我们通过记录每一天的三种可能状态来逐步计算：

1. 持有股票（hold）：表示当天我们手中有股票的情况下，最大可能的收益。
2. 未持有股票但不在冷冻期（unhold）：表示当天我们手中没有股票，并且可以自由操作的情况下，最大可能的收益。
3. 未持有股票且处于冷冻期（cooldown）：表示当天我们手中没有股票，但因为刚卖出，处于冷冻期的情况下，最大可能的收益。

状态转移

• 持有股票（hold）：

  • 要么昨天已经持有股票，今天保持不动（收益不变）。
  • 要么昨天没有股票（并且不在冷冻期），今天买入股票（收益减去今天的价格）。
  • 状态转移公式：

• 未持有股票但不在冷冻期（unhold）：

  • 要么昨天已经没有股票且不在冷冻期，今天也不操作（收益不变）。
  • 要么昨天刚结束冷冻期，今天自由操作（收益等于昨天冷冻期的收益）。
  • 状态转移公式：

• 未持有股票且处于冷冻期（cooldown）：

  • 必须是昨天持有股票，今天卖出进入冷冻期（收益增加今天的价格）。
  • 状态转移公式：

初始化

• 第一天持有股票：hold[0] = -stocks[0]（买入股票后收益为负）。
• 第一天未持有股票且不在冷冻期：unhold[0] = 0（什么都不做，收益为 0）。
• 第一天未持有股票且处于冷冻期：cooldown[0] = 0（第一天不可能处于冷冻期）。

最终结果

最后一天的最大利润一定是：

因为只有未持有股票时，收益才可能是最大值。

---

三、代码实现

public class Main {public static int solution(int[] stocks) {if (stocks == null || stocks.length == 0) {return 0; // 没有数据时，最大收益为 0}// 初始化第 1 天的三种状态int hold = -stocks[0];      // 第一天买入股票，收益为负的价格int unhold = 0;            // 第一天不持有股票，收益为 0int cooldown = 0;          // 第一天冷冻期不可能发生，收益为 0// 从第 2 天开始计算for (int i = 1; i < stocks.length; i++) {// 暂存之前的状态值，用于计算int prevHold = hold;int prevUnhold = unhold;int prevCooldown = cooldown;// 更新持有股票状态hold = Math.max(prevHold, prevUnhold - stocks[i]);// 更新未持有股票且不在冷冻期状态unhold = Math.max(prevUnhold, prevCooldown);// 更新未持有股票且处于冷冻期状态cooldown = prevHold + stocks[i];}// 最终结果是未持有股票的两种状态的最大值return Math.max(unhold, cooldown);}public static void main(String[] args) {// 测试用例System.out.println(solution(new int[]{1, 2})); // 输出 1System.out.println(solution(new int[]{2, 1})); // 输出 0System.out.println(solution(new int[]{1, 2, 3, 0, 2})); // 输出 3System.out.println(solution(new int[]{2, 3, 4, 5, 6, 7})); // 输出 5System.out.println(solution(new int[]{1, 6, 2, 7, 13, 2, 8})); // 输出 12}
}

---

执行流程解析

以输入数组 [1, 2, 3, 0, 2] 为例，逐步计算各状态：

天数	持有股票（hold）	未持有股票且无冷冻期（unhold）	未持有股票且冷冻期（cooldown）
1	-1	0	0
2	-1	0	1
3	-1	1	2
4	1	2	-1
5	1	2	3

最终结果为：max(unhold[4], cooldown[4]) = 3。

---

时间和空间复杂度

1. 时间复杂度：每一天的计算是常数操作，时间复杂度为 O(n)，其中 n 是数组的长度。
2. 空间复杂度：只用到了常数个变量，空间复杂度为 O(1)。

我们通过动态规划，把问题分解为三个状态，分别计算每天的最佳选择。

博客