个人认为这是一道非常精巧的动归题目。
The alternating sum of a 0-indexed array is defined as the sum of the elements at even indices minus the sum of the elements at odd indices.
For example, the alternating sum of [4,2,5,3] is (4 + 5) - (2 + 3) = 4.
Given an array nums, return the maximum alternating sum of any subsequence of nums (after reindexing the elements of the subsequence).
A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements’ relative order.For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.
if __name__ == '__main__':
arr = list(map(int, input().split(' ')))
n = len(arr)
dp_max = [0 for i in range(n)]
dp_min = [0 for i in range(n)]
# initialize
if n > 0:
dp_max[-1] = max(0, arr[-1])
dp_min[-1] = min(0, arr[-1])
if n > 1:
dp_max[-2] = max(0, arr[-1], arr[-2], arr[-2] - arr[-1])
dp_min[-2] = min(0, arr[-1], arr[-2], arr[-2] - arr[-1])
for i in range(n-3, -1, -1):
dp_max[i] = max(dp_max[i+1], arr[i]-dp_min[i+1])
dp_min[i] = min(dp_min[i+1], arr[i]-dp_max[i+1])
print(dp_max[0])
