package leetcode;

/**
 * https://leetcode.com/problems/maximum-alternating-subsequence-sum/
 */
public class Problem1911 {
    public long maxAlternatingSum(int[] nums) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem1911 prob = new Problem1911();
        System.out.println(prob.maxAlternatingSum(new int[]{4,2,5,3})); // 7
        System.out.println(prob.maxAlternatingSum(new int[]{5,6,7,8})); // 8
        System.out.println(prob.maxAlternatingSum(new int[]{6,2,1,2,4,5})); // 10
    }
}

package leetcode;

/**
 * https://leetcode.com/problems/maximum-alternating-subsequence-sum/
 */
public class Problem1911 {
    public long maxAlternatingSum(int[] nums) {
        return maxAlternatingSum(nums, 0, true, new Long[nums.length][2]);
    }

    private static long maxAlternatingSum(int[] nums, int i, boolean odd, Long[][] memo) {
        if (i == nums.length) {
            return 0;
        }
        if (memo[i][odd ? 0 : 1] != null) {
            return memo[i][odd ? 0 : 1];
        }
        long a = maxAlternatingSum(nums, i + 1, !odd, memo) + (odd ? nums[i] : -nums[i]);
        long b = maxAlternatingSum(nums, i + 1, odd, memo);
        long max = Math.max(a, b);
        memo[i][odd ? 0 : 1] = max;
        return max;
    }
}

Solve problem 1911