package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/stone-game-ii/
 */
public class Problem1140 {
    public int stoneGameII(int[] piles) {
        int totalSum = 0;
        for (int pile : piles) {
            totalSum += pile;
        }
        return stoneGame(piles, 1, 0, totalSum, new HashMap<>());
    }

    private static int stoneGame(int[] piles, int m, int index, int totalSum, Map<String, Integer> memo) {
        String key = m + "," + index;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        int answer = 0;
        for (int i = 1; i <= 2 * m; i++) {
            int sum = 0;
            for (int j = index; j < index + i && j < piles.length; j++) {
                sum += piles[j];
                int value = totalSum - stoneGame(piles, Math.max(i, m), j + 1, totalSum - sum, memo);
                answer = Math.max(answer,  value);
            }
        }
        memo.put(key, answer);
        return answer;
    }

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

@@ -341,19 +341,51 @@
 new 
-HashMap%3C%3E()
+Integer%5Bpiles.length * 2%5D%5Bpiles.length + 1%5D
 );%0A 
@@ -471,28 +471,16 @@
 Sum,
- Map%3CString,
  Integer
 %3E me
@@ -479,9 +479,12 @@
 eger
-%3E
+%5B%5D%5B%5D
  mem
@@ -500,71 +500,34 @@
     
-String key = m + %22,%22 + index;%0A        if (memo.containsKey(key)
+if (memo%5Bindex%5D%5Bm%5D != null
 ) %7B%0A
@@ -553,17 +553,18 @@
 memo
-.get(key)
+%5Bindex%5D%5Bm%5D
 ;%0A  
@@ -599,55 +599,8 @@
  0;%0A
-        for (int i = 1; i %3C= 2 * m; i++) %7B%0A    
     
@@ -612,28 +612,24 @@
 nt sum = 0;%0A
-    
         for 
@@ -633,17 +633,17 @@
 or (int 
-j
+i
  = index
@@ -644,17 +644,17 @@
  index; 
-j
+i
  %3C index
@@ -660,14 +660,20 @@
 x + 
-i
+(2 * m)
  && 
-j
+i
  %3C p
@@ -685,17 +685,17 @@
 length; 
-j
+i
 ++) %7B%0A  
@@ -704,20 +704,16 @@
         
-   
- 
 sum += p
@@ -721,16 +721,12 @@
 les%5B
-j
+i
 %5D;%0A
-    
     
@@ -787,15 +787,27 @@
 ax(i
+ - index + 1
 , m), 
-j
+i
  + 1
@@ -831,20 +831,16 @@
  memo);%0A
-    
         
@@ -882,22 +882,8 @@
 e);%0A
-            %7D%0A
     
@@ -904,593 +904,51 @@
 memo
-.put(key, answer);%0A        return answer;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1140 prob = new Problem1140();%0A        System.out.println(prob.stoneGameII(new int%5B%5D%7B2, 3, 9, 4%7D)); // 6%0A        System.out.println(prob.stoneGameII(new int%5B%5D%7B2, 7, 9, 4, 4%7D)); // 10%0A        System.out.println(prob.stoneGameII(new int%5B%5D%7B2, 3, 4%7D)); // 5%0A        System.out.println(prob.stoneGameII(new int%5B%5D%7B2%7D)); // 2%0A        System.out.println(prob.stoneGameII(new int%5B%5D%7B2, 3%7D)); // 5%0A        System.out.println(prob.stoneGameII(new int%5B%5D%7B6, 4, 2, 8, 1, 8, 6, 6, 2%7D)); // 24
+%5Bm%5D%5Bindex%5D = answer;%0A        return answer;
 %0A   

Solve problem 1140