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

# 借鉴买卖股票三的答案  把 5 换成 2k + 1 + 1


import sys

inputs = []
for line in sys.stdin:
    a = line.split()
    inputs.append(a)
    
n = int(inputs[0][0])
k = int(inputs[0][1])
P = [int(x) for x in inputs[1]]

if k > n / 2:
    # 则相当于买卖股票 (二), 此处贴 (二) 里的代码
    dp = 0
    for i in range(1, n):
        if P[i] > P[i - 1]:
            dp += P[i] - P[i - 1]
    print(dp)
else:
    dp = [[0] * (2 * k + 1 + 1) for _ in range(n + 1)]

    # 初始条件
    dp[0][1] = 0
    for j in range(2, 2 * k + 2):
        dp[0][j] = -float('inf')

    for i in range(1, n + 1):
        # 1, 3, 5
        for j in range(1, 2 * k + 2, 2):
            # dp[i][j] = max{dp[i-1][j], dp[i-1][j-1] + (P[N-1] - P[N-2])}
            dp[i][j] = dp[i-1][j]
            if j > 1 and i >= 2 and dp[i-1][j-1] != -float('inf'):
                dp[i][j] = max(dp[i][j], dp[i-1][j-1] + (P[i-1] - P[i-2]))

        # 2, 4
        for j in range(2, 2 * k + 1, 2):
            # dp[i][j] = max{dp[i-1][j] + (P[N-1] - P[N-2]), dp[i-1][j-1], dp[i-1][j-2] + (P[N-1] - P[N-2])}
            dp[i][j] = dp[i-1][j-1]
            if i > 1 and dp[i-1][j] != -float('inf'):
                dp[i][j] = max(dp[i][j], dp[i-1][j] + (P[i-1] - P[i-2]))

            if j > 2 and i >= 2 and dp[i-1][j-2] != -float('inf'):
                dp[i][j] = max(dp[i][j], dp[i-1][j-2] + (P[i-1] - P[i-2]))

    out = 0
    for j in range(1, 2 * k + 2, 2):
        out = max(out, dp[n][j])

    print(out)