A row of paper lanterns hangs over a street; lantern i has brightness values[i]. Lanterns are released one at a time, in any order you choose. Releasing a lantern scores left * values[i] * right, where left and right are the brightness of its current neighbours that are still hanging (use 1 if there is no neighbour on that side). After release the two neighbours become adjacent. Return the largest total score for releasing all lanterns.
Examples
Input: values = [2, 4, 3]
Output: 33
Explanation: release 4 (2*4*3 = 24), then 2 (1*2*3 = 6), then 3 (1*3*1 = 3).
Input: values = [5]
Output: 5
Constraints
0 <= len(values) <= 1000 <= values[i] <= 100- There are
n!release orders; aim for O(n**3).
Goals
- Choose the last event in an interval to make the subproblems independent
- Pad the sequence with sentinel values for the boundaries