本文最后更新于 366 天前,其中的信息可能已经有所发展或是发生改变。
题目描述:
给定一个整数数组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
解法一:动态规划
算法思路:
定义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)。