题解 | #买卖股票的最好时机(四)# Python+解释

import sys

# 每天都有 2k个状态，即第一次买入， 第一次卖出

# 用 buy 和 sell 来累计之前k次买入卖出的钱

# sell[k] 为第k卖出最大收益， buy[k]为第k次买入最大收益

# sell[k] = max(buy[k-1] + prices[i], sell[k])

# buy[k] = max(sell[k-1]-prices[i], buy[j])

n, k = list(map(int,input().strip().split(' ')))

prices = list(map(int,input().strip().split(' ')))

sell =[0]*k 
buy = [-prices[0]]*k 


for i in range(1,n):
    buy[0] = max(-prices[i], buy[0]) # 第一次买入
    sell[0] = max(sell[0],buy[0]+prices[i])
    for j in range(1,k):
        buy[j] = max(sell[j-1]-prices[i], buy[j]) 
        sell[j] = max(buy[j]+prices[i], sell[j])
print(sell[-1] if sell[-1]>0 else 0)