package leetcode;

/**
 * https://leetcode.com/problems/burst-balloons/
 */
public class Problem312 {
    public int maxCoins(int[] nums) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem312 prob = new Problem312();
        System.out.println(prob.maxCoins(new int[]{3, 1, 5, 8})); // 167
    }
}

@@ -12,16 +12,116 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0Aimport java.util.HashMap;%0Aimport java.util.List;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -245,32 +245,1403 @@
     
-// TODO%0A        return 0
+List%3CInteger%3E list = new ArrayList%3C%3E();%0A        for (int num : nums) %7B%0A            list.add(num);%0A        %7D%0A        Map%3CString, Integer%3E memo = new HashMap%3C%3E();%0A        return maxCoins(list, 0, memo);%0A    %7D%0A%0A    private int maxCoins(List%3CInteger%3E nums, int accu, Map%3CString, Integer%3E memo) %7B%0A        if (nums.size() == 1) %7B%0A            return nums.get(0);%0A        %7D%0A        String key = nums.toString();%0A        if (memo.containsKey(key)) %7B%0A            return memo.get(key);%0A        %7D%0A        int max = 0;%0A        for (int i = 0; i %3C nums.size(); i++) %7B%0A            int left = 1;%0A            int right = 1;%0A            if (i - 1 %3E= 0) %7B%0A                left = nums.get(i - 1);%0A            %7D%0A            if (i + 1 %3C nums.size()) %7B%0A                right = nums.get(i + 1);%0A            %7D%0A            int val = left * nums.get(i) * right;%0A            List%3CInteger%3E newNums = new ArrayList%3C%3E();%0A            newNums.addAll(nums.subList(0, i));%0A            newNums.addAll(nums.subList(i + 1, nums.size()));%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//            System.out.println(%22 - after=%22 + newNums);%0A            max = Math.max(max, maxCoins(newNums, accu, memo) + val);%0A        %7D%0A        memo.put(key, max);%0A        return max
 ;%0A  
@@ -1730,24 +1730,26 @@
 oblem312();%0A
+//
         Syst
@@ -1809,16 +1809,197 @@
  // 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
     %7D%0A%7D%0A

Update problem 312