if __name__ =="__main__":
n = int(input())
data = list(map(int,input().split()))
up = [0]*n
down = [0]*n
dp = [0]*n
up[0] = data[0]
down[0] = data[0]
dp[0] = max(up[0],down[0])
if n>1:
up[1] = max(up[0]-data[1],data[1])
down[1] = data[0] - data[1]
dp[1] = max(up[1],down[1])
if n>2:
for i in range(2,n):
up[i] = max(up[i-2]-data[i-1],0)+data[i]
down[i] = down[i-2]+data[i-1]-data[i]
dp[i] = max(up[i],down[i])
print(max(dp))
自测了几组数据都可以得到正确结果，时间复杂度为O(n)，空间复杂度为O(n)
全部评论
(4) 回帖