输入：nums = [4,2,5,3]
输出：7
解释：最优子序列为 [4,2,5] ，交替和为 (4 + 5) - 2 = 7 。

/**
 * nums 给定的数组
 * cur 遍历过程中的当前索引
 * len 数组长度，递归终止条件
 * val 到cur位置得到的交替和结果
 * flag 正负1，用于控制交替和的符号
 * value 结果数组，用于保存最后的交替和结果
 **/
void getAlternatingSubSequenceSum(int[] nums, int cur, int len, int val, int flag, List<Integer> value)

class Solution {
    public long maxAlternatingSum(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int n = nums.length;
        getAlternatingSubSequenceSum(nums, 0, n, 0, 1, list);
        int max = 0;
        for (int v : list) {
            max = Math.max(v, max);
        }
        return max;
    }

    // 获取所有子序列的交替和
    public void getAlternatingSubSequenceSum(int[] nums, int cur, int len, int val, int flag, List<Integer> value) {
        if (cur == len) {
            value.add(val);
            return;
        }
        // flag控制符号
        int add =val + flag * nums[cur]; // 当前元素保留
        getAlternatingSubSequenceSum(nums, cur + 1, len, add, -flag, value);
        int next = val; // 当前元素不保留
        getAlternatingSubSequenceSum(nums, cur + 1, len, next, flag, value);
    }
}

class Solution {
    public long maxAlternatingSum(int[] nums) {
        long even = nums[0], odd = 0;
        for (int i = 1; i < nums.length; i++) {
            even = Math.max(even, odd + nums[i]);
            odd = Math.max(odd, even - nums[i]);
        }
        return even;
    }
}