image.png
0. 链接
1. 题目
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
2. 思路1: 动态规划
- 记录dp[k][i] 表示最多用k次卖出机会, 截止到第i天的最大收益
- 状态转移方程
dp[k][i] = max(dp[k][i - 1], prices[i] - (prices[j] - dp[k - 1][j - 1]))
含义是在第i天, 可以选择卖出，也可以选择不卖出
- 选择卖出, 则卖出的这笔在第j天买入, 则需要使得第j天的买入累计成本(即包含第j天的买入价, 再扣除之前赚得的利润)最小, 即使得prices[j] - dp[k - 1][j - 1]最小
- 选择不卖出, 则第i天的利润, 跟第i-1天的例如没区别, 即dp[k][i - 1]
最佳利润则要取这两个值的较大值
- 时间复杂度: ```O(KN)``
- 空间复杂度:
O(KN)
3. 代码
# coding:utf8
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
dp = [[0] * len(prices) for _ in range(3)]
for k in range(1, 3):
min_cost = prices[0]
for i in range(1, len(prices)):
price = prices[i]
# 看做第k次交易的最小成本(成本要扣除前面赚的钱)
min_cost = min(min_cost, price - dp[k - 1][i - 1])
# 第i天不卖出, 则利润等同于第i-1天的; 若卖出, 则获利price-min_cost
dp[k][i] = max(dp[k][i - 1], price - min_cost)
return dp[2][len(prices) - 1]
def my_test(solution, prices):
print('input: {}; output: {}'.format(prices, solution.maxProfit(prices)))
solution = Solution()
my_test(solution, [3, 3, 5, 0, 0, 3, 1, 4])
my_test(solution, [2, 1, 2, 0, 1])
my_test(solution, [1, 2, 4, 2, 5, 7, 2, 4, 9, 0])
输出结果
input: [3, 3, 5, 0, 0, 3, 1, 4]; output: 6
input: [2, 1, 2, 0, 1]; output: 2
input: [1, 2, 4, 2, 5, 7, 2, 4, 9, 0]; output: 13
4. 结果
image.png
5. 思路2: 简化版动态规划
- 只有两次交易机会, 则可以通过记录buy1, profit1, buy2, profit2
- 然后遍历一次数组, 不断最小化buy1和buy2, 同时最大化profit1和profit2, 其中buy2又要扣除之前的累计利润profit1
- 于是最终获得的profit2就是最大累计利润
- 时间复杂度
O(KN) - 空间复杂度
O(KN)
6. 代码
# coding:utf8
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
buy1 = buy2 = prices[0]
profit1 = profit2 = 0
for price in prices:
buy1 = min(buy1, price)
profit1 = max(profit1, price - buy1)
buy2 = min(buy2, price - profit1)
profit2 = max(profit2, price - buy2)
return profit2
def my_test(solution, prices):
print('input: {}; output: {}'.format(prices, solution.maxProfit(prices)))
solution = Solution()
my_test(solution, [3, 3, 5, 0, 0, 3, 1, 4])
my_test(solution, [2, 1, 2, 0, 1])
my_test(solution, [1, 2, 4, 2, 5, 7, 2, 4, 9, 0])
输出结果为
input: [3, 3, 5, 0, 0, 3, 1, 4]; output: 6
input: [2, 1, 2, 0, 1]; output: 2
input: [1, 2, 4, 2, 5, 7, 2, 4, 9, 0]; output: 13
7. 结果
image.png
