题目描述:
给定一个数组,它的第 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
提示:
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^5
解法一:动态规划
算法思路:
由于只能进行两次交易,且必须在完成第一笔交易后才能进行第二笔交易,因此,定义以下四个变量:
- buy1:进行了第一次买操作。
- sell1:进行了第一次卖操作,即完成了第一笔交易。
- buy2:进行了第二次买操作。
- sell2:进行了第二次卖操作,即完成了第二笔交易。
对于 buy1
而言,在第 i
天可以不进行任何操作,也可以以 prices[i]
的价格买入股票,那么得到 buy1
的状态转移方程:
$$
\text{{buy}}_1 = \max(\text{{buy}}_1’, -\text{{prices}}[i])
$$
其中buy1’表示第i-1天的状态
对于 sell1
而言,在第 i
天可以不进行任何操作,也可以在进行了第一次买的操作的前提下以 prices[i]
的价格卖出股票,那么得到 sell1
的状态转移方程:
$$
\text{{sell}}_1 = \max(\text{{sell}}_1’, \text{{buy}}_1’ + \text{{prices}}[i])
$$
同理可得到 buy2
和 sell2
的状态转移方程:
$$
\text{{buy}}_2 = \max(\text{{buy}}_2’, \text{{sell}}_1’ – \text{{prices}}[i])
$$
$$ \text{{sell}}_2 = \max(\text{{sell}}_2’, \text{{buy}}_2’ + \text{{prices}}[i]) $$
由于在同一天买入并且卖出这一操作带来的收益为0,不影最终答案,因此状态转移方程可以写为:
$$
\text{{buy}}_1 = \max(\text{{buy}}_1, -\text{{prices}}[i])
$$
$$
\text{{sell}}_1 = \max(\text{{sell}}_1, \text{{buy}}_1 + \text{{prices}}[i])
$$
$$
\text{{buy}}_2 = \max(\text{{buy}}_2, \text{{sell}}_1 – \text{{prices}}[i])
$$
$$
\text{{sell}}_2 = \max(\text{{sell}}_2, \text{{buy}}_2 + \text{{prices}}[i])
$$
最后的答案为 sell2
。
代码实现:
class Solution {
public int maxProfit(int[] prices) {
int buy1 = -prices[0], sell1 = 0;
int buy2 = -prices[0], sell2 = 0;
for(int i = 1; i < prices.length; i++){
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
}
return sell2;
}
}
复杂度分析:
时间复杂度: O(n),其中 n 为数组 prices 的长度。
空间复杂度: O(1)