Remove Boxes


The runtime of the code is indeed
O(n^4)
, and the bound is tight in the worst case. Consider the following test case of100
numbers in total:1, 2, 1, 2, ... 1, 2, 1, 2 (25 copies of 1, 2) followed by 1, 1, 1, ... 1, 1, 1 (25 copies of 1) followed by 2, 2, 2, ... 2, 2, 2 (25 copies of 2).
If you add a counter in the forloop of the DP call, you will get a total number like 1547375 for such a test case, which is way more than 100^3. If
n = 200
, the counter is24,866,625
vs 200^3 =8,000,000
, etc.However, if we ONLY loop through those boxes[i] that are equal to boxes[r], then the runtime can be proved to be
O(n^3)
.
This can be done via a preprocessing inO(n^3)
time as well.

I agree with @htrinh that the While loop should be modified accordingly. The While loop seems to be considering repetitions on the Left of the region instead of the right region.
As a side note, to consider the question with "how many repetitions there are to the LEFT of the region", the while loop is the same as in the code, but the transition part is to be changed to:
for (int i = r; i >= l+1; i) { if (boxes[i] == boxes[l]) { dp[l][r][k] = max(dp[l][r][k], calculatePoints(boxes, dp, i, r, k+1) + calculatePoints(boxes, dp, l+1, i1, 0)); } }


@lixx2100
I don't feel that O(n^3) time can be achieved.For input like 12121212121..... each [l,r] pairing can have every k <=(rl+1)/2 and for each of those subproblems they would still iterate over (rl+1)/2 or so i which match r.
Are you sure O(n^3) is possible?