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)
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.
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.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 10
1 <= boxes.length <= 50
1 <= boxes[i] <= 100
Time Limit: 1 sec
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:
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:
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:
Randomly Sorted
Merge Two Sorted Arrays Without Extra Space
Ninja And The Strictly Increasing Array
Negative To The End
8-Queen Problem