题目
买卖股票时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 示例 2: 输入: prices = [1] 输出: 0
提示：
1 <= prices.length <= 5000 0 <= prices[i] <= 1000
题解
解题分析
题解思路
- 由题意可知，我们最多只能同时买入一支股票，并且卖出股票后又冷冻期的限制，在某一天我们有三种不同的状态:
- 我们目前持有一支股票，对应的「累计最大收益」记为 f0；
- 我们目前不持有任何股票，并且处于冷冻期中，对应的「累计最大收益」记为 f1
- 我们目前不持有任何股票，并且不处于冷冻期中，对应的「累计最大收益」记为 f2
- 那么我们就围绕三种状态进行分析。
- 如果当前持有股票最大收益
f0 = max(f1, f2 - price[i]) - 如果当天难处于冷冻期当前最大收益
f1 = f0 + price[i] - 如果当天不处于冷冻期中，丹铅最大收益为
f2 = max(f1, f2)
- 我们只需要通过循环不断的去计算三个值，最后返回合适的结果即可
复杂度分析
- 时间复杂度：O(N)
- 空间复杂度：O(1), 我们没有创建额外的数组来存储。
解题代码
题解代码如下（代码中有详细的注释说明）：
class Solution { public int maxProfit(int[] prices) { // 判断有效的参数 if (prices == null || prices.length == 0) { return 0; } // 获取数组长读 int n = prices.length; // f0, f1, f2 默认值分别是 -prices[0], 0, 0 // 因为第一天是负收益 int f0 = -prices[0], f1 = 0, f2 = 0; for (int i = 1; i < n; i++) { int newf0 = Math.max(f0, f2 - prices[i]); int newf1 = f0 + prices[i]; int newf2 = Math.max(f1, f2); f0 = newf0; f1 = newf1; f2 = newf2; } return Math.max(f1, f2); } }
提交后反馈结果：
