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

@@ -177,32 +177,73 @@
     
-// TODO%0A        return 0
+return maxAlternatingSum(nums, 0, true, new Long%5Bnums.length%5D%5B2%5D)
 ;%0A  
@@ -256,21 +256,22 @@
    p
-ublic
+rivate
  static 
 void
@@ -270,316 +270,479 @@
 tic 
-void main(String%5B%5D args) %7B%0A        Problem1911 prob = new Problem1911();%0A        System.out.println(prob.maxAlternatingSum(new int%5B%5D%7B4,2,5,3%7D)); // 7%0A        System.out.println(prob.maxAlternatingSum(new int%5B%5D%7B5,6,7,8%7D)); // 8%0A        System.out.println(prob.maxAlternatingSum(new int%5B%5D%7B6,2,1,2,4,5%7D)); // 10
+long maxAlternatingSum(int%5B%5D nums, int i, boolean odd, Long%5B%5D%5B%5D memo) %7B%0A        if (i == nums.length) %7B%0A            return 0;%0A        %7D%0A        if (memo%5Bi%5D%5Bodd ? 0 : 1%5D != null) %7B%0A            return memo%5Bi%5D%5Bodd ? 0 : 1%5D;%0A        %7D%0A        long a = maxAlternatingSum(nums, i + 1, !odd, memo) + (odd ? nums%5Bi%5D : -nums%5Bi%5D);%0A        long b = maxAlternatingSum(nums, i + 1, odd, memo);%0A        long max = Math.max(a, b);%0A        memo%5Bi%5D%5Bodd ? 0 : 1%5D = max;%0A        return max;
 %0A   

Solve problem 1911