Box Annihilation

Hard

0/120

0 upvote

Asked in company

Problem statement

You are given a list of N boxes, each represented by a positive integer indicating its color.

You can remove boxes in a series of rounds. In each round, you can choose a contiguous group of k boxes of the same color. Removing this group gives you k * k points. After removal, the boxes to the left and right of the removed group (if any) become adjacent.

Your goal is to find the maximum possible total score you can achieve by removing all the boxes.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'N', the number of boxes.

The second line contains 'N' space-separated integers, representing the colors of the boxes.

Output Format:

Print a single integer representing the maximum achievable score.

Note:

A simple greedy approach does not work. The optimal strategy often involves removing other boxes first to bring same-colored boxes together, forming a larger contiguous group for a much higher score later.

This problem requires a specific type of dynamic programming with a 3D state to handle this "grouping" mechanic:
    dp[left][right][k] = The maximum score you can get from the sub-array boxes[left...right], assuming you already have k boxes of the same color as boxes[left] attached to its left side, ready to be grouped.

Sample Input 1:

9
1 3 2 2 2 3 4 3 1

Sample Output 1:

Explanation for Sample 1:

An optimal sequence of removals is:
1.  `[1, 3, 2, 2, 2, 3, 4, 3, 1]` -> Remove the three '2's. Score += 3*3 = 9.
    Remaining: `[1, 3, 3, 4, 3, 1]`
2.  `[1, 3, 3, 4, 3, 1]` -> Remove the single '4'. Score += 1*1 = 1.
    Remaining: `[1, 3, 3, 3, 1]`
3.  `[1, 3, 3, 3, 1]` -> Remove the three '3's. Score += 3*3 = 9.
    Remaining: `[1, 1]`
4.  `[1, 1]` -> Remove the two '1's. Score += 2*2 = 4.
    Remaining: `[]`
Total Score = 9 + 1 + 9 + 4 = 23.

Sample Input 2:

3
1 1 1

Sample Output 2:

Explanation for Sample 2:

Remove all three '1's in one go. Score = 3 * 3 = 9.

Expected Time Complexity:

The expected time complexity is O(N^3).

Constraints:

1 <= N <= 100
1 <= boxes[i] <= 100

Time limit: 1 sec

Approaches (1)

Approach 1

Box Annihilation

Time Complexity

Space Complexity

(100% EXP penalty)

Box Annihilation

Console