本文最后更新于 366 天前，其中的信息可能已经有所发展或是发生改变。
题目描述：
给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
提示：
1 <= prices.length <= 50000 <= prices[i] <= 1000
解法一：动态规划
算法思路：
定义dp[i][j]表示第 i 天，持有股票状态为 j 时，能够获得的最大利润，其中 j = 0时表示不持有股票，j = 1 时表示持有股票。
初始时，dp[0][0] = 0，dp[0][1] = -prices[0]。
当 i > 0 时，有以下两种情况：
- 第
i天不持有股票，可能是第i - 1天不持有股票且在第i天不进行任何操作，或者在第i - 1天持有股票且在第i天卖出，因此dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])。 - 第
i天持有股票，可能是第i - 1天持有股票且在第i天不进行任何操作，或者在第i - 2天不持有股票且在第i天买入，因此dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])。
综上得到状态转移方程： $$ dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) $$
$$ dp[i][1] = max(dp[i-1][1], dp[i-2][0] – prices[i]) $$
答案即为 dp[n-1][0]。
代码实现：
lass Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][1] = -prices[0];
for(int i = 1; i < n; i++){
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], (i>1?dp[i-2][0]:0)-prices[i]);
}
return dp[n-1][0];
}
}
由于dp[i][]的转移只和dp[i-1][]和dp[i-2][]有关，因此可以使用三个变量 dp，dp0，dp1 来代替数组 dp，优化空间复杂度：
class Solution {
public int maxProfit(int[] prices) {
int dp = 0, dp0 = 0, dp1 = -prices[0];
for(int i = 1; i < prices.length; i++){
int temp = Math.max(dp0, dp1 + prices[i]);
dp1 = Math.max(dp1, dp - prices[i]);
dp = dp0;
dp0 = temp;
}
return dp0;
}
}
复杂度分析：
时间复杂度： O(n)，其中 n 为数组 prices 的长度。
空间复杂度： O(1)。
