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;
}
}