package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.com/problems/burst-balloons/
 */
public class Problem312 {
    public int maxCoins(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        Map<String, Integer> memo = new HashMap<>();
        return maxCoins(list, memo);
    }

    private int maxCoins(List<Integer> nums, Map<String, Integer> memo) {
        if (nums.size() == 1) {
            return nums.get(0);
        }
        String key = nums.toString();
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        int max = 0;
        for (int i = 0; i < nums.size(); i++) {
            int left = 1;
            int right = 1;
            if (i - 1 >= 0) {
                left = nums.get(i - 1);
            }
            if (i + 1 < nums.size()) {
                right = nums.get(i + 1);
            }
            int val = left * nums.get(i) * right;

            int tmp = nums.get(i);
//            System.out.println("index=" + i);
//            System.out.println(" - before=" + nums);
//            System.out.println(" - val=" + val + " (" + left + " * " + nums.get(i) + " * " + right + ")");
            nums.remove(i);
//            System.out.println(" - after=" + nums);
            max = Math.max(max, maxCoins(nums, memo) + val);
            nums.add(i, tmp);
        }
        memo.put(key, max);
        return max;
    }

    public static void main(String[] args) {
        Problem312 prob = new Problem312();
        System.out.println(prob.maxCoins(new int[]{3, 1, 5, 8})); // 167
//        System.out.println(prob.maxCoins(new int[]{2, 4, 8})); // 88
//        System.out.println(prob.maxCoins(new int[]{2, 4, 8, 4, 0, 7, 8, 9, 1, 2, 4, 7, 1, 7, 3, 6})); // 3304
//        System.out.println(prob.maxCoins(new int[]{8, 2, 6, 8, 9, 8, 1, 4, 1, 5, 3, 0, 7, 7, 0, 4, 2})); // 3414
    }
}

@@ -431,16 +431,36 @@
 ns(list,
+ 0, list.size() - 1,
  memo);%0A
@@ -478,16 +478,23 @@
 private 
+static 
 int maxC
@@ -517,16 +517,36 @@
 r%3E nums,
+ int start, int end,
  Map%3CStr
@@ -583,24 +583,19 @@
 if (
-nums.size() == 1
+start %3E end
 ) %7B%0A
@@ -617,19 +617,9 @@
 urn 
-nums.get(0)
+0
 ;%0A  
@@ -651,23 +651,25 @@
 y = 
-nums.toString()
+start + %22%7C%22 + end
 ;%0A  
@@ -772,60 +772,8 @@
  0;%0A
-        for (int i = 0; i %3C nums.size(); i++) %7B%0A    
     
@@ -786,28 +786,24 @@
 t left = 1;%0A
-    
         int 
@@ -821,25 +821,25 @@
         
-   
- 
 if (
-i
+start
  - 1 %3E= 
@@ -839,28 +839,24 @@
 - 1 %3E= 0) %7B%0A
-    
             
@@ -871,17 +871,21 @@
 ums.get(
-i
+start
  - 1);%0A 
@@ -891,33 +891,26 @@
         
-    %7D%0A   
+%7D%0A
         
  if (i +
@@ -905,14 +905,15 @@
     
- 
 if (
-i
+end
  + 1
@@ -942,20 +942,16 @@
         
-   
- 
 right = 
@@ -959,17 +959,19 @@
 ums.get(
-i
+end
  + 1);%0A 
@@ -973,28 +973,24 @@
 1);%0A        
-   
- 
 %7D%0A          
@@ -991,468 +991,202 @@
     
-    int val = left * nums.get(i) * right;%0A%0A            int tmp = nums.get(i);%0A//            System.out.println(%22index=%22 + i);%0A//            System.out.println(%22 - before=%22 + nums);%0A//            System.out.println(%22 - val=%22 + val + %22 (%22 + left + %22 * %22 + nums.get(i) + %22 * %22 + right + %22)%22);%0A            nums.remove(i);%0A//            System.out.println(%22 - after=%22 + nums);%0A            max = Math.max(max, maxCoins(nums, memo) + val);%0A            nums.add(i, tmp
+for (int i = start; i %3C= end; i++) %7B%0A            int val = left * nums.get(i) * right;%0A            int a = maxCoins(nums, start, i - 1, memo);%0A            int b = maxCoins(nums, i + 1, end, memo
 );%0A 
@@ -1194,526 +1194,136 @@
     
-  %7D%0A
       
-  memo.put(key, max);%0A        return max;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem312 prob = new Problem312();%0A        System.out.println(prob.maxCoins(new int%5B%5D%7B3, 1, 5, 8%7D)); // 167%0A//        System.out.println(prob.maxCoins(new int%5B%5D%7B2, 4, 8%7D)); // 88%0A//        System.out.println(prob.maxCoins(new int%5B%5D%7B2, 4, 8, 4, 0, 7, 8, 9, 1, 2, 4, 7, 1, 7, 3, 6%7D)); // 3304%0A//        System.out.println(prob.maxCoins(new int%5B%5D%7B8, 2, 6, 8, 9, 8, 1, 4, 1, 5, 3, 0, 7, 7, 0, 4, 2%7D)); // 3414
+int total = a + val + b;%0A            max = Math.max(max, total);%0A        %7D%0A        memo.put(key, max);%0A        return max;
 %0A   

Solve problem 312