Clearing Colored Cubes

Hard

A row of cubes is laid out, and the color of each cube is a positive number in the array cubes. In one move you pick any contiguous stretch of cubes that are all **the same color** and remove the whole stretch. If it held t cubes, you earn t · t points. The remaining cubes close the gap, so the cubes on either side of the removed stretch become neighbors. You keep making moves until the row is empty. Return the maximum total score you can achieve.

Example 1

cubes=[3, 1, 1, 3, 2, 3] → 14

Remove the two 1s (4 points), then the 2 (1 point): the three 3s meet and give 9 points. Total 4 + 1 + 9 = 14.

Example 2

cubes=[5, 5, 5, 5] → 16

All cubes share a color, so one move clears them: 4 · 4 = 16.

Example 3

cubes=[1, 2, 3] → 3

No two cubes match, so each one is worth 1 point.

Constraints

1 ≤ len(cubes) ≤ 100
1 ≤ cubes[i] ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Memoization Array Dynamic Programming

Similar problems

Every Way to Space the Words Hard Longest Uphill Walk Hard Six-Cell Tile Slider Hard Cutting a Berry Cake Hard Other Orders for the Same Search Tree Hard

Input

cubes=[3, 1, 1, 3, 2, 3]

Expected

Run checks the first 3 tests in your browser. Submit checks all 125 tests on the server, hidden ones included.