124. Remove Boxes

Given boxes with colors (integers), remove boxes to maximize points. Removing k contiguous same-color boxes earns k*k points. Return the maximum points achievable.

Input: An integer array of box colors.

Output: Integer — max points.

Examples

Input: [1,3,2,2,2,3,4,3,1]
Output: 23
Explanation: Optimal removals yield 23.

Input: [1,1,1]
Output: 9
Explanation: 3*3=9.

Input: [1]
Output: 1
Explanation: 1*1=1.

Constraints

• 0<=n<=100
• 1<=boxes[i]<=100

Asked by