package leetcode;

/**
 * https://leetcode.com/problems/predict-the-winner/
 */
public class Problem486 {
    public boolean PredictTheWinner(int[] nums) {
        PlayerSum ps = predict(nums, 0, nums.length - 1, Player.P2);
        System.out.println(ps.player + " " + ps.sum);
        return false;
    }

    private static class PlayerSum {
        private final Player player;
        private final int sum;

        public PlayerSum(Player player, int sum) {
            this.player = player;
            this.sum = sum;
        }
    }

    private static PlayerSum predict(int[] nums, int start, int end, Player p) {
        if (start == end) {
            return new PlayerSum(p, 0);
        }
        Player nextPlayer = (p == Player.P1) ? Player.P2 : Player.P1;
        PlayerSum ps1 = predict(nums, start + 1, end, nextPlayer);
        PlayerSum ps2 = predict(nums, start, end - 1, nextPlayer);

        int a = nums[start] + Math.min(ps1.sum, ps2.sum);
        int b = nums[end] + Math.min(ps1.sum, ps2.sum);
        int max = Math.max(a, b);
        // TODO
        return null;
    }

    private enum Player {
        P1, P2
    }

    public static void main(String[] args) {
        Problem486 prob = new Problem486();
        System.out.println(prob.PredictTheWinner(new int[]{1, 5, 2})); // false
//        System.out.println(prob.PredictTheWinner(new int[]{1, 5, 233, 7})); // true
    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -210,380 +210,190 @@
     
-PlayerSum ps = predict(nums, 0, nums.length - 1, Player.P2);%0A        System.out.println(ps.player + %22 %22 + ps.sum);%0A        return false;%0A    %7D%0A%0A    private static class PlayerSum %7B%0A        private final Player player;%0A        private final int sum;%0A%0A        public PlayerSum(Player player, int sum) %7B%0A            this.player = player;%0A            this.sum 
+int sum = 0;%0A        for (int num : nums) %7B%0A            sum += num;%0A        %7D%0A        int val = predict(nums, 0, nums.length - 1, new HashMap%3C%3E());%0A        return val %3E
 = 
+(
 sum
-;%0A        %7D
+ - val);
 %0A   
@@ -415,25 +415,19 @@
  static 
-PlayerSum
+int
  predict
@@ -463,16 +463,33 @@
 nd, 
-Player p
+Map%3CString, Integer%3E memo
 ) %7B%0A
@@ -506,18 +506,17 @@
  (start 
-==
+%3E
  end) %7B%0A
@@ -538,27 +538,9 @@
 urn 
-new PlayerSum(p, 0)
+0
 ;%0A  
@@ -559,161 +559,160 @@
     
-Player nextPlayer = (p == Player.P1) ? Player.P2 : Player.P1;%0A        PlayerSum ps1 = predict(nums, start + 1, end, nextPlayer);%0A        PlayerSum ps2 = 
+String key = start + %22%7C%22 + end;%0A        if (memo.containsKey(key)) %7B%0A            return memo.get(key);%0A        %7D%0A        int a = nums%5Bstart%5D + Math.min(
 pred
@@ -730,88 +730,77 @@
 tart
+ + 2
 , end
- - 1, nextPlayer);%0A%0A        int a = 
+, memo),%0A            predict(
 nums
-%5B
+, 
 start
-%5D
  + 
-Math.min(ps1.sum, ps2.sum
+1, end - 1, memo)
 );%0A 
@@ -840,406 +840,179 @@
 in(p
-s1.s
+redict(n
 um
+s
 , 
-ps2.sum);%0A        int max = Math.max(a, b);%0A        // TODO%0A        return null;%0A    %7D%0A%0A    private enum Player %7B%0A        P1, P2
+start, end - 2, memo),%0A            predict(nums, start + 1, end - 1, memo));
 %0A    
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem486 prob = new Problem486();%0A        System.out.println(prob.PredictTheWinner(new int%5B%5D%7B1, 5, 2%7D)); // false%0A//        System.out.println(prob.PredictTheWinner(new int%5B%5D%7B1, 5, 233, 7%7D)); // true
+int max = Math.max(a, b);%0A        memo.put(key, max);%0A        return max;
 %0A   

Solve problem 486