package com.fishercoder.solutions;

/**
 * 486. Predict the Winner
 *
 * Given an array of scores that are non-negative integers.
 * Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on.
 * Each time a player picks a number, that number will not be available for the next player.
 * This continues until all the scores have been chosen.
 * The player with the maximum score wins.
 * Given an array of scores, predict whether player 1 is the winner.
 * You can assume each player plays to maximize his score.

 Example 1:
 Input: [1, 5, 2]
 Output: False
 Explanation: Initially, player 1 can choose between 1 and 2.
 If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
 So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
 Hence, player 1 will never be the winner and you need to return False.

 Example 2:
 Input: [1, 5, 233, 7]
 Output: True
 Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
 Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

 Note:
 1 <= length of the array <= 20.
 Any scores in the given array are non-negative integers and will not exceed 10,000,000.
 If the scores of both players are equal, then player 1 is still the winner.
 */
public class _486 {

    /**credit: https://discuss.leetcode.com/topic/76312/java-1-line-recursion-solution
     * Explanation
     So assuming the sum of the array it SUM, so eventually player1 and player2 will split the SUM between themselves.
     For player1 to win, he/she has to get more than what player2 gets.
     If we think from the prospective of one player, then what he/she gains each time is a plus,
     while, what the other player gains each time is a minus. Eventually if player1 can have a >0 total, player1 can win.

     Helper function simulate this process. In each round:
     if e==s, there is no choice but have to select nums[s]
     otherwise, this current player has 2 options:
     --> nums[s]-helper(nums,s+1,e): this player select the front item, leaving the other player a choice from s+1 to e
     --> nums[e]-helper(nums,s,e-1): this player select the tail item, leaving the other player a choice from s to e-1
     Then take the max of these two options as this player's selection, return it.*/
    public boolean predictTheWinner(int[] nums) {
        return helper(nums, 0, nums.length - 1, new Integer[nums.length][nums.length]) >= 0;
    }

    private int helper(int[] nums, int start, int end, Integer[][] mem) {
        if (mem[start][end] == null) {
            mem[start][end] = start == end ? nums[end] :
                    Math.max(nums[end] - helper(nums, start, end - 1, mem),
                            nums[start] - helper(nums, start + 1, end, mem));
        }
        return mem[start][end];
    }

}

@@ -1496,19 +1496,71 @@
  %7B%0A%0A    
-/**
+public static class Solution1 %7B%0A        /**%0A         * 
 credit: 
@@ -1636,16 +1636,20 @@
 on%0A     
+    
 * Explan
@@ -1659,16 +1659,22 @@
 on%0A     
+   
+ * 
 So assum
@@ -1783,16 +1783,22 @@
 es.%0A    
+     *
  For pla
@@ -1862,16 +1862,22 @@
 s.%0A     
+   
+ * 
 If we th
@@ -1964,16 +1964,22 @@
 us,%0A    
+     *
  while, 
@@ -2088,21 +2088,38 @@
 an win.%0A
-%0A
+         * %0A   
     
+  *
  Helper 
@@ -2170,16 +2170,22 @@
 d:%0A     
+   
+ * 
 if e==s,
@@ -2236,16 +2236,22 @@
 s%5D%0A     
+   
+ * 
 otherwis
@@ -2288,24 +2288,30 @@
 ptions:%0A    
+     *
  --%3E nums%5Bs%5D
@@ -2419,16 +2419,22 @@
  e%0A     
+   
+ * 
 --%3E nums
@@ -2543,16 +2543,22 @@
 e-1%0A    
+     *
  Then ta
@@ -2627,19 +2627,33 @@
 turn it.
-*/%0A
+%0A         */%0A    
     publ
@@ -2698,24 +2698,28 @@
 ) %7B%0A        
+    
 return helpe
@@ -2795,19 +2795,27 @@
  0;%0A    
-%7D%0A%0A
+    %7D%0A%0A    
     priv
@@ -2888,16 +2888,20 @@
         
+    
 if (mem%5B
@@ -2919,24 +2919,28 @@
  == null) %7B%0A
+    
             
@@ -3004,16 +3004,20 @@
         
+   
+ 
 Math.max
@@ -3064,16 +3064,20 @@
 , mem),%0A
+    
         
@@ -3158,18 +3158,25 @@
     
-%7D%0A
+    %7D%0A   
         
 retu
@@ -3167,24 +3167,25 @@
 %0A           
+ 
 return mem%5Bs
@@ -3196,16 +3196,26 @@
 %5D%5Bend%5D;%0A
+        %7D%0A
     %7D%0A%0A%7D

refactor 486