Remove Boxes

Posted: 23 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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:

  1. 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.
  2. 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.
  3. 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’
  4. We finally return the ‘MAX_PROFIT’.
Try Problem