Remove Boxes

PROBLEM STATEMENT

You are given several boxes with different colours represented by different positive numbers. For moving the boxes you can remove them in multiple iterations until there are no boxes left. Now, every time you can choose some continuous boxes with the same color (i.e., composed of 'k' boxes, 'k' >= 1), remove them and get 'k' * 'k' points for removing them.

Your task for the problem is to find and return the maximum points you can get by removing those boxes.

For Example:

Input: boxes = [1, 3, 2, 2, 2, 3, 4, 3, 1]
Output: 23
Explanation:
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (Remove 3 boxes with number 2, 3*3=9 points) 
----> [1, 3, 3, 3, 1] (Remove one box with number 4, 1*1=1 points) 
----> [1, 1] (Remove 3 boxes with number 3, 3*3=9 points) 
----> [] (2*2=4 points)

Input Format:

The first line of input contains a single integer ‘T’ denoting the number of test cases that would be there.

The first line of each test case contains a single integer ‘N’ denoting the number of boxes that would be given.

And the next line contains ‘N’ space-separated integers which are the colors of the boxes represented as integers.

Output Format :

For each test case, print the maximum points that could be collected by removing the boxes of the same color from the list.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= boxes.length <= 50
1 <= boxes[i] <= 100

Time Limit: 1 sec

Approach 1

Approach: The idea here is to store the repeated set of sub solutions for the problem. Then return the solution you already have calculated the value for recursively building the lookup table.

The algorithm will be:

The first conditions would be to handle the base cases which are when the list of boxes either have no boxes when we return a profit to be 0 while if there is only one box then a max profit of 1 is returned by the function.
Now, while we iterate through the list of boxes keeping track of the starting index ‘START_INDEX’ and the ending index ‘END_INDEX’ of the continuous set of boxes that we are able to find.
Initialise a ‘MAX_PROFIT’ variable with 0 and for those set of boxes, we check if there is a continuous set of boxes having the same colour in the following manner:-
- Store the box at the ‘START_INDEX’ in a variable ‘PREV_BOX’ and also initialise a ‘BOX_COUNT’ with a value of 0.
- Now until the ‘END_INDEX’ of the boxes is less than the length of the boxes in the list and the colour of the boxes are continuously the same as the colour of ‘PREV_BOX’ we iterate through the boxes and keep incrementing the value of ‘END_INDEX’ and ‘BOX_COUNT’.
- If the ‘END_INDEX’ becomes greater than or equal to the length of the boxes we try to maximise the profit by
  1. ‘MAX_PROFIT’ = max(‘MAX_PROFIT’, (‘BOX_COUNT’ * ‘BOX_COUNT’))
- Otherwise, the profit would be as follows:
  1. ‘MAX_PROFIT’ = max(‘MAX_PROFIT’, maximizePointsByRemovingBoxes(boxes[0:’START_INDEX��] + boxes[‘END_INDEX’:’length_of_boxes’]) + (‘BOX_COUNT’ * ‘BOX_COUNT’))
- At the end of each iteration, update the ‘START_INDEX’ as the ‘END_INDEX’
We finally return the ‘MAX_PROFIT’.

Try Problem

Approach 2

Approach: The idea here is that one natural approach is to consider mem(i, j) = the answer for A[i: j+1]. But this isn't flexible enough to divide and conquer style strategies. For example, with [1,2,2,2,1], we don't have enough information when investigating things like [1,2,2,2] and [1] separately.

The algorithm will be:

First, initialise a 3-D ‘MEM’ list (array) with 0s.
Now store the values of all box removals possible from a starting index to an ending index including all of the boxes that can be removed in each iteration through a function call taking the following parameters:
- DFS(boxes, start_index, sizeofboxes, number_of_boxes_initially_selected).
Now inside the DFS function check:
- Return 0 if ‘START_INDEX’ becomes greater than the ‘END_INDEX’.
- Return the already calculated value of maximum points if there is any present inside our ‘MEM’ list for a ‘START_INDEX’, ‘END_INDEX’ and a specific number of selected boxes for removal (K).
- Otherwise, store the value of maximum points that can be collected by:
  - Dp[l][r][k] = DFS(boxes, l, r - 1, 0) + (k + 1)*(k + 1)
- Now we iterate for the boxes present in the list from start index ‘l’ upto end index ‘r’ and check if there exists a continuous set of boxes with the same colour available.
- if we find same color box, then we have a chance to get a higher value by group BOXES[l] ~ BOXES[i] and BOXES[r] together, plus the value from BOXES[i + 1] ~ BOXES[r - 1].
After the iterations are complete, finally return the MEM[l][r][k] which contain the maximum possible values from the sub-problems.

Try Problem

Approach 3

Approach: The idea here is that you initialize a three-dimensional dp list (array), ‘k’ (streak), left, right can be in any order because the iteration guarantees the 3d array is filled starting from entries that represent the base cases with list (array) length of 1. In iterative dp, we have to put left and right as the first two dimensions for the same reason.

The algorithm will be:

The first optimization which can be done is using a global ‘DP’ table/dictionary which would store the set of profits that we can get for different box lengths that we would iteratively traverse.
We return the profit for a particular box list length for which we might already have a calculated value of profit, we start building up our 3-D ‘DP’ list (array/table), calculating the profits for different combinations of selecting a specific continuous set of boxes for removal and store the respective.
Now, while we iterate through the list of boxes keeping track of the starting index ‘START_INDEX’ and the ending index ‘END_INDEX’ of the continuous set of boxes that we are able to find.
Initialize an end index ‘R’ with the value of the starting length of the box with the initially one box of length one selected ('R' = l + length) and for those set of boxes, we check if there is a continuous set of boxes having the same color in the following manner:-
- Store the maximum profit that can be obtained by selecting a continuous set of boxes of length ‘K’ up to the maximum boxes that we can select up to the value of the starting index ‘l’ selected and store it in a variable ‘RES’.
- Now until the ‘END_INDEX’ of the boxes is less than the length of the boxes in the list and the color of the boxes are continuously the same as the color of ‘PREV_BOX’ we iterate through the boxes and keep incrementing the value of ‘end_index’ and keep on calculating the maximum points that we could get by selecting those boxes and keep updating ‘RES’.
- If the ‘END_INDEX’ becomes greater than or equal to the length of the boxes we try to maximize the profit by
  - ‘RES’ = max(‘RES’, DP[l + 1][i - 1][0] + DP[i][r][STREAK + 1])
For every calculated value of the profit maximised for a particular set of box lengths, we can store it inside our ‘DP’ table/dictionary at DP[l][r][k].
We finally return the ‘DP[0][N - 1][0]’.

Try Problem