[LeetCode] Burst Ballons

Reference: https://leetcode.com/discuss/72216/share-some-analysis-and-explanations

public class Solution {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] ballons = new int[nums.length+2];
        int index = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) ballons[index++] = nums[i];
        }
        ballons[0] = ballons[index] = 1;
        int[][] maximumPoints = new int[index+1][index+1];
        for (int stepLength = 2; stepLength <= index; stepLength++) {
            for (int left = 0; left <= index - stepLength; left++) {
                int right = left + stepLength;
                for (int i = left + 1; i < right; i++) {
                    maximumPoints[left][right] = Math.max(maximumPoints[left][right], maximumPoints[left][i] + maximumPoints[i][right] + ballons[left]*ballons[i]*ballons[right]);
                }
            }
        }
        return maximumPoints[0][index];
    }
}