Maximum Alternating Subsequence Sum

定义一个alternating subsequence sum为偶数相加减去奇数相减的和. 求最大的一个.

这题就是找两个上下波动的本地最值, 用dp做, 选的方法只有从当前最大的even或者odd选或者不选.

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