题目描述
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意： 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例：
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股价 = 0）的时候买入，在第 6 天（股价 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3。
随后，在第 7 天（股价 = 1）的时候买入，在第 8 天（股价 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3。
方法一：动态规划
解题步骤
- 定义状态：
dp[i][j]表示第i天完成j笔交易的最大利润。 - 初始化状态：
dp[0][1]和dp[0][2]都初始化为负无穷，表示不可能完成交易。 - 状态转移：
- 第
i天完成一笔交易的最大利润：dp[i][1] = max(dp[i-1][1], -prices[i]) - 第
i天完成两笔交易的最大利润：dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])
- 第
- 结果输出：
max(dp[n-1][1], dp[n-1][2])
Python 示例
def maxProfit(prices):
n = len(prices)
if n == 0:
return 0
dp = [[0] * 3 for _ in range(n)]
dp[0][1] = -prices[0]
dp[0][2] = float('-inf')
for i in range(1, n):
dp[i][1] = max(dp[i-1][1], -prices[i])
dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])
return max(0, dp[n-1][2])
# Example usage
prices = [3,3,5,0,0,3,1,4]
print(maxProfit(prices)) # Output: 6
算法分析
- 时间复杂度：O(N)，其中 N 是数组的长度。
- 空间复杂度：O(N)，用于存储 dp 数组。
算法图解与说明
初始: dp = [[-3, -inf], [0, 0], [0, 0], ...]
第一天: 不操作，买入 -3
第二天: 不操作，维持 -3
第三天: 不操作，维持 -3
第四天: 不操作，买入 0
第五天: 不操作，维持 0
第六天: 卖出 +3
第七天: 买入 1
第八天: 卖出 +4
方法二：状态机优化
解题步骤
- 使用四个变量表示不同状态下的最大利润：
buy1,sell1,buy2,sell2。 - 初始状态设为：
buy1 = buy2 = -inf,sell1 = sell2 = 0。 - 更新状态机：
buy1: 第一次买入的最大利润sell1: 第一次卖出的最大利润buy2: 第二次买入的最大利润sell2: 第二次卖出的最大利润
Python 示例
def maxProfit(prices):
buy1, sell1, buy2, sell2 = float('-inf'), 0, float('-inf'), 0
for price in prices:
buy1 = max(buy1, -price)
sell1 = max(sell1, buy1 + price)
buy2 = max(buy2, sell1 - price)
sell2 = max(sell2, buy2 + price)
return sell2
# Example usage
prices = [3,3,5,0,0,3,1,4]
print(maxProfit(prices)) # Output: 6
算法分析
- 时间复杂度：O(N)
- 空间复杂度：O(1)
算法图解与说明
状态更新过程：
初始: buy1 = -inf, sell1 = 0, buy2 = -inf, sell2 = 0
价格迭代: 3 -> buy1 = -3
3 -> sell1 = 0
5 -> sell1 = 2
0 -> buy2 = 2
0 -> 维持
3 -> sell2 = 5
1 -> 维持
4 -> sell2 = 6
这两种方法为买卖股票问题的高级解法，适用于有多次交易机会的场景。
方法三：左右扫描数组法
解题步骤
- 使用两个数组
left_profits和right_profits。left_profits[i]存储从第一天到第i天的最大利润，right_profits[i]存储从第i天到最后一天的最大利润。 - 从左到右遍历一遍股价数组，更新
left_profits为到当前日为止的最大利润。 - 从右到左遍历股价数组，更新
right_profits为从当前日到结束的最大利润。 - 最终结果为某一天两边利润之和的最大值。
Python 示例
def maxProfit(prices):
n = len(prices)
if n <= 1:
return 0
left_profits = [0] * n
right_profits = [0] * n
# 左侧最小值初始化
min_price = prices[0]
for i in range(1, n):
left_profits[i] = max(left_profits[i-1], prices[i] - min_price)
min_price = min(min_price, prices[i])
# 右侧最大值初始化
max_price = prices[n-1]
for i in range(n-2, -1, -1):
right_profits[i] = max(right_profits[i+1], max_price - prices[i])
max_price = max(max_price, prices[i])
# 计算两边利润的最大和
max_profit = 0
for i in range(n):
max_profit = max(max_profit, left_profits[i] + right_profits[i])
return max_profit
# Example usage
prices = [3,3,5,0,0,3,1,4]
print(maxProfit(prices)) # Output: 6
算法分析
- 时间复杂度：O(N)，其中 N 是数组的长度。
- 空间复杂度：O(N)，需要两个长度为 N 的数组来存储左右两侧的最大利润。
算法图解与说明
股票价格: [3, 3, 5, 0, 0, 3, 1, 4]
左侧利润: [0, 0, 2, 2, 2, 2, 2, 2]
右侧利润: [3, 3, 3, 3, 3, 3, 3, 0]
最大利润: 每天两侧利润之和的最大值为 6 (第 6 天)
方法四：改进的状态机方法
解题步骤
- 减少状态机方法中变量的使用，只使用两个变量跟踪到目前为止的最大利润。
- 遍历价格数组时，更新四个关键状态：第一次买入、第一次卖出、第二次买入和第二次卖出的最大利润。
- 通过逐步更新这四个状态来最大化最终的利润。
Python 示例
def maxProfit(prices):
first_buy, first_sell = float('-inf'), 0
second_buy, second_sell = float('-inf'), 0
for price in prices:
first_buy = max(first_buy, -price)
first_sell = max(first_sell, first_buy + price)
second_buy = max(second_buy, first_sell - price)
second_sell = max(second_sell, second_buy + price)
return second_sell
# Example usage
prices = [3,3,5,0,0,3,1,4]
print(maxProfit(prices)) # Output: 6
算法分析
- 时间复杂度：O(N)，N 是股票价格数组的长度。
- 空间复杂度：O(1)，使用常数空间。
算法图解与说明
初始状态: first_buy = -inf, first_sell = 0, second_buy = -inf, second_sell = 0
更新过程:
- 第1天: first_buy 更新为 -3
- 第2天: 无变化
- 第3天: first_sell 更新为 2
- 第4天: second_buy 更新为 2
- 第5天: 无变化
- 第6天: second_sell 更新为 5
- 第7天: 无变化
- 第8天: second_sell 更新为 6
以上四种方法各有优势，适用于不同的场景和优化需求。可以根据具体需要选择最合适的解决方案。