<p>You are given several <code>boxes</code> with different colors represented by different positive numbers.</p>

<p>You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (i.e., composed of <code>k</code> boxes, <code>k &gt;= 1</code>), remove them and get <code>k * k</code> points.</p>

<p>Return <em>the maximum points you can get</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> boxes = [1,3,2,2,2,3,4,3,1]
<strong>Output:</strong> 23
<strong>Explanation:</strong>
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----&gt; [1, 3, 3, 4, 3, 1] (3*3=9 points) 
----&gt; [1, 3, 3, 3, 1] (1*1=1 points) 
----&gt; [1, 1] (3*3=9 points) 
----&gt; [] (2*2=4 points)
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> boxes = [1,1,1]
<strong>Output:</strong> 9
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> boxes = [1]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= boxes.length &lt;= 100</code></li>
	<li><code>1 &lt;= boxes[i]&nbsp;&lt;= 100</code></li>
</ul>

class Solution {
public:
    using int2 = array<int, 2>; // (length, color)
    int n = 0;                  // for B.size()
    vector<int2> B;
    int freq[101] = {0};
    void build_B(vector<int>& boxes) {
        int prev = boxes[0], bz = boxes.size();
        B.push_back({1, prev});
        freq[prev]++;
        n++;
        for (int i = 1; i < bz; i++) {
            int curr = boxes[i];
            freq[curr]++;
            if (curr == prev) {
                B.back()[0]++;
            } else {
                prev = boxes[i];
                B.push_back({1, prev});
                n++;
            }
        }
    //    cout << B.size() << ", n=" << n << endl;
    }
    int removeFreq1(vector<int2>& B) {
        int idx = 0, rmv = 0;
        for (int i = 0; i < n; i++) {
            auto b = B[i];
            if (freq[b[1]] > 1)
                B[idx++] = b;
            else {
                if (i > 0 && i + 1 < n && B[i - 1][1] == B[i + 1][1]) {
                    B[idx-1][0] += B[i + 1][0]; // merge 2 same color segments
                    i++;                      //  skip next i
                }
                rmv++;
            }
        }
        n = idx;
        B.resize(n);
        return rmv;
    }
    vector<vector<vector<int>>> dp;

    int f(int i, int j, int k, vector<int2>& B) {
        if (i > j) return 0;  // Base case: no valid segment
        if (dp[i][j][k] != -1)
            return dp[i][j][k];
        if (i == j)
            return dp[i][j][k] = (B[i][0] + k) * (B[i][0] + k);

        int ans = f(i, j - 1, 0, B) + (B[j][0] + k) * (B[j][0] + k);
        for (int m = i; m < j; m++) {
            if (B[m][1] == B[j][1]) {
                ans = max(ans, f(i, m, B[j][0] + k, B) + f(m + 1, j - 1, 0, B));
            }
        }
        return dp[i][j][k] = ans;
    }

    int removeBoxes(vector<int>& boxes) {
    //    cout<<boxes.size()<<endl;
        build_B(boxes);
        int cnt = removeFreq1(B);
    //    cout << n << endl;
        dp.assign(n, vector(n, vector<int>(100, -1)));
        int a;
        a= f(0, n-1, 0, B);
        return cnt + a;
    }
};
37251