卜东波.算法设计与分析：Maximum Alternating Subsequence Sum（Python实现）

卜东波.算法设计与分析：Maximum Alternating Subsequence Sum（Python实现）

个人认为这是一道非常精巧的动归题目。

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])