The naive approach involves exploring every possible removal sequence. At any step, we can identify all contiguous groups of identical boxes and try removing each group, then recursively solve for the remaining array.

Naive Algorithm Logic

1. Scan the current array configuration.
2. Identify all contiguous segments of the same color.
3. For each segment, remove it and calculate the score ($k^2$).
4. Concatenate the remaining left and right parts to form a new array.
5. Recurse on the new array.
6. Return the maximum score among all choices.

python
# Pseudo-code for Brute Force
def solve(boxes):
    if not boxes: return 0
    max_score = 0
    groups = get_groups(boxes) # returns list of (start, end, length)
    
    for start, end, length in groups:
        current_points = length * length
        new_boxes = boxes[:start] + boxes[end+1:]
        max_score = max(max_score, current_points + solve(new_boxes))
        
    return max_score

Complexity Analysis

The time complexity of this approach is difficult to express strictly but is roughly factorial or exponential relative to $N$. With $N=100$, the branching factor is large, and the recursion depth can be up to $N$. Without memoization, we re-calculate the same sub-problems (identical array states) repeatedly. This inevitably leads to a Time Limit Exceeded (TLE) error.

Core Insight for Remove Boxes

The primary challenge in LeetCode 546 is that the optimal score for a subarray boxes[i...j] depends on information outside that subarray.

Consider the array [A, B, A]. If we are solving for the subarray containing only B (index 1 to 1), the optimal decision depends on whether the As at index 0 and 2 will eventually merge. If we define our DP state strictly as dp[i][j] (max score for range $i$ to $j$), we lose the context that boxes[i] might be combined with boxes of the same color that appeared before $i$ (which became adjacent because intermediate boxes were removed).

To fix this, we must expand the state space. We add a third dimension, $k$, representing the number of boxes identical to boxes[i] that are currently attached to the left of index $i$ (from the previously processed prefix).

The Invariant: $dp[i][j][k]$ represents the maximum score for the subarray boxes[i...j], assuming there are already $k$ boxes of the same color as boxes[i] attached to the left of $i$.

This allows us to make a local decision at boxes[i] that accounts for accumulated history without needing to know the exact structure of that history—only the count matters for the $k^2$ calculation.

Algorithm Strategy: DP - Interval DP

We define a recursive function with memoization solve(l, r, k):

• l (left): The start index of the current subarray.
• r (right): The end index of the current subarray.
• k: The number of boxes with the same color as boxes[l] that are virtually attached to the left of l.

State Transitions

For the state (l, r, k), we have two primary strategic choices regarding boxes[l]:

1. Remove boxes[l] immediately: We combine boxes[l] with the $k$ attached boxes. We remove this entire block of $k+1$ boxes.

   • Points gained: $(k+1)^2$.
   • Remaining problem: solve(l + 1, r, 0).

2. Delay removal to merge with a future box: We keep boxes[l] (and its $k$ attached friends) waiting. We look for an index $m$ inside the range $(l, r]$ such that boxes[m] has the same color as boxes[l].

   • If we find such an , we can try to clear out the boxes between and (the range ).

We take the maximum of Option 1 and all valid scenarios of Option 2.

Execution Flow

1. Initialization: Create a memoization table memo[N][N][N] initialized to 0 or -1. Call the helper function solve(0, N-1, 0).
2. Base Case: If $l > r$, return 0 (no boxes left).
3. Memoization Check: If memo[l][r][k] is already computed, return it.
4. Optimization (Grouping):
   • While l + 1 <= r and boxes[l] == boxes[l+1]:
     • Increment l and k.
   • This groups consecutive identical boxes immediately, reducing recursion depth and redundant calculations.
5. Calculate Option 1 (Remove Now):
   • res = (k + 1)^2 + solve(l + 1, r, 0)
6. Calculate Option 2 (Merge):
   • Iterate through index $m$ from $l + 1$ to $r$.
   • If boxes[m] == boxes[l]:
     • res = max(res, solve(l + 1, m - 1, 0) + solve(m, r, k + 1))
7. Store and Return: Save res to memo[l][r][k] and return it.

Proof of Correctness

The correctness relies on the principle of optimality in Dynamic Programming.

1. State Completeness: The tuple $(l, r, k)$ completely describes the decision boundaries. The variable $k$ captures the only external dependency (accumulated length) required to calculate the score.
2. Transition Exhaustiveness: At any point l, we either cash out the current chain of color boxes[l] immediately, or we extend the chain by jumping over a different-colored segment to the next occurrence of the same color. There are no other ways to form a contiguous block of boxes[l]'s color.
3. Substructure: By taking the maximum of all valid splits (removing now vs. merging with any valid $m$), we guarantee finding the global maximum for the current state.

Reference Implementation

C++ Solution for LeetCode 546

cpp
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

class Solution {
public:
    int memo[100][100][100];

    int solve(vector<int>& boxes, int l, int r, int k) {
        if (l > r) return 0;
        
        // Return cached value if it exists
        if (memo[l][r][k] > 0) return memo[l][r][k];
        
        int original_l = l;
        int original_k = k;

        // Optimization: Group continuous identical boxes
        while (l + 1 <= r && boxes[l] == boxes[l + 1]) {
            l++;
            k++;
        }
        
        // Option 1: Remove the current group of (k+1) boxes
        int res = (k + 1) * (k + 1) + solve(boxes, l + 1, r, 0);
        
        // Option 2: Try to merge with matching boxes later in the array
        for (int m = l + 1; m <= r; ++m) {
            if (boxes[m] == boxes[l]) {
                // Determine score by clearing the middle part (l+1 to m-1)
                // and merging the current group with the group at m
                res = max(res, solve(boxes, l + 1, m - 1, 0) + solve(boxes, m, r, k + 1));
            }
        }
        
        // Restore l and k for memoization key consistency if needed, 
        // though strictly memoizing based on the optimized l/k is also valid and often preferred.
        // Here we memoize the state after the while-loop optimization to avoid re-scanning.
        return memo[original_l][r][original_k] = res;
    }

    int removeBoxes(vector<int>& boxes) {
        memset(memo, 0, sizeof(memo));
        return solve(boxes, 0, boxes.size() - 1, 0);
    }
};

Java Solution for LeetCode 546

java
class Solution {
    int[][][] memo;

    public int removeBoxes(int[] boxes) {
        int n = boxes.length;
        memo = new int[n][n][n];
        return solve(boxes, 0, n - 1, 0);
    }

    private int solve(int[] boxes, int l, int r, int k) {
        if (l > r) return 0;
        
        if (memo[l][r][k] > 0) return memo[l][r][k];

        int i = l; 
        int currentK = k;
        
        // Optimization: Skip consecutive identical boxes
        while (i + 1 <= r && boxes[i] == boxes[i + 1]) {
            i++;
            currentK++;
        }

        // Option 1: Remove the current block
        int res = (currentK + 1) * (currentK + 1) + solve(boxes, i + 1, r, 0);

        // Option 2: Merge with future occurrences
        for (int m = i + 1; m <= r; m++) {
            if (boxes[m] == boxes[i]) {
                // We clear the middle (i+1 to m-1) and carry over currentK+1 counts to m
                res = Math.max(res, solve(boxes, i + 1, m - 1, 0) + solve(boxes, m, r, currentK + 1));
            }
        }

        return memo[l][r][k] = res;
    }
}

Python Solution for LeetCode 546

python
class Solution:
    def removeBoxes(self, boxes: list[int]) -> int:
        n = len(boxes)
        # Memoization table initialized to 0
        memo = [[[0] * n for _ in range(n)] for _ in range(n)]

        def solve(l, r, k):
            if l > r:
                return 0
            
            if memo[l][r][k] > 0:
                return memo[l][r][k]
            
            original_l, original_k = l, k
            
            # Optimization: Group consecutive boxes of the same color
            while l + 1 <= r and boxes[l] == boxes[l + 1]:
                l += 1
                k += 1
            
            # Option 1: Remove the current group immediately
            res = (k + 1) * (k + 1) + solve(l + 1, r, 0)
            
            # Option 2: Try to merge with a box of the same color later in the range
            for m in range(l + 1, r + 1):
                if boxes[m] == boxes[l]:
                    # Clear the gap (l+1 to m-1) and merge k+1 boxes into index m
                    res = max(res, solve(l + 1, m - 1, 0) + solve(m, r, k + 1))
            
            memo[original_l][r][original_k] = res
            return res

        return solve(0, n - 1, 0)