Shatter the Crystals
A row of crystals has the energies listed in energy. Shattering a crystal releases its energy times the energies of its current left and right neighbors, the nearest crystals still in the row; a missing neighbor counts as 1. The shattered crystal leaves the row, so the crystals on either side of it become neighbors.
Shatter every crystal, one at a time, in any order you like. Return the largest total energy you can release. An empty row releases 0.
Example 1
Shatter the 4 first (2 * 4 * 3 = 24), then the 2 (1 * 2 * 3 = 6), then the 3 (1 * 3 * 1 = 3): 33 in total.
Example 2
Shatter the two 1s first (9 + 81), then one 9 (1 * 9 * 9 = 81) and finally the other 9 (9): 180.
Constraints
0 <= len(energy) <= 300 <= energy[i] <= 100
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Two Pickers Down the FieldHard
- Two Towers of One HeightHard
- Factorials Up to nBeginner
- Fibonacci NumberBeginner
- Frog Across the StonesBeginner
- Hop One or ThreeBeginner
- N-th Tribonacci NumberBeginner
- Paving With Colored SlabsBeginner