Instead of thinking about which item to remove first, consider which item is removed last within a given range.

Burst Balloons

hard

Acceptance: 43%

Dynamic Programming

An array of positive integers represents a line of items, each labeled with a score. When you remove item i, you earn score[i-1] score[i] score[i+1] points. Boundary items that are out of range count as having a score of 1. Determine the maximum total points achievable by removing all items.

Examples

Example 1:

Input:nums = [2,4,3,5]

Output:110

Explanation: An optimal removal order yields the maximum of 110 points.

Example 2:

Input:nums = [1,5]

Output:10

Explanation: Remove 1 first (1*1*5=5), then 5 (1*5*1=5). Total = 10.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Burst Balloons

Examples

Hints

Related Problems