给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。
示例 2:
输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
在股票系列的第三个题中,,规定的股票交易次数为2。而这个题中是股票交易次数k为任意值。因此可以直接用上一题的代码:买卖股票的最佳时机|||
不过需要优化一下,否则会超内存。
考虑一次股票买卖,第一天买入,第二天卖出,因此一次股票买卖需要两天。当给定的k大于len(prices)//2时,只要后一天的价格大于前一天的价格,就进行一次股票买卖。反正是不会超过限制的股票交易次数。当k小于len(prices)//2时,就可以利用上一题的代码,不过得需要修正一下。
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if len(prices) == 0:
return 0
if k >= len(prices)//2:
profit = 0
for i in range(len(prices)-1):
if prices[i+1] > prices[i]:
profit += (prices[i+1]-prices[i])
return profit
else:
n = len(prices)
dp = [[[0 for i in range(2)] for i in range(k+1)] for i in range(n)]
for i in range(k+1):
# 不管k等于几,第0天不持有股票的利润为0,持有股票的利润为-prices[0](卖股票的钱)
dp[0][i][0] = 0
dp[0][i][1] = -prices[0]
for i in range(1,n):
for j in range(1,k+1):
dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j][1] + prices[i])
dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j-1][0] - prices[i])
return dp[n-1][k][0]