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

动态规划,二维 dp, 两个维度一是天数，二是持有状态; dp[i][0] 表示第 i 天未持有的最大收益, dp[i][1] 表示第 i 天持有的最大收益 转移方程为: dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]) dp[i][1] = max(dp[i - 1[1], dp[i - 1][0] - prices[i]) 由于 k 是一次, 故 dp[i][1] = max(dp[i - 1[1], - prices[i])

import sys
n = int(sys.stdin.readline().strip())
prices = list(map(int, sys.stdin.readline().strip().split()))
dp = [[0 for _ in range(2)] for _ in range(n)]
dp[0][1] = -prices[0]
for i in range(1, n):
    dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
    dp[i][1] = max(dp[i - 1][1], -prices[i])

print(dp[-1][0])