FunctionRacerProblemsRace

Shatter the Crystals

HardDynamic programmingPython, JavaScript, TypeScript, Java, C++

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

energy [2,4,3]
returns 33

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

energy [9,1,1,9]
returns 180

Shatter the two 1s first (9 + 81), then one 9 (1 * 9 * 9 = 81) and finally the other 9 (9): 180.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems