The height of the tower is calculated by adding the width of all the coins used in the formation of this tower.
The first line contains a single integer ‘T’ representing the number of test cases. The first line of each test case will contain a single integer ‘N’ which denotes the number of coins available. The next ‘N’ lines contain the two space-separated integers “ARR[i]” and “ARR[i]”, where “ARR[i]” is the width of the ‘i-th’ coin and “ARR[i]” is the diameter of the ‘i-th’ coin.
For each test case, return the maximum possible height of the tower. Output for every test case will be printed in a separate line.
You don’t need to print anything; It has already been taken care of. Just implement the given function.
1 <= T <= 50 1 <= N <= 10^4 1 <= ARR[i] and ARR[i] <= 10^5 Time limit: 1 sec
The basic idea is to first sort the given array/list of integers in the increasing order of width and then just find the longest increasing subsequence of coins on the basis of their diameter.
We are here using a helper function that is recursive in nature and it is used to find the LIS (Longest Increasing Subsequence) of coins on the basis of diameter.
int helper(vector<vector<int>> &arr, int previous, int current)
Where ‘ARR’ is the vector/list of pairs of integers that contain all the given coins (width of the coins of first and diameter on second), ‘PREVIOUS’ is the maximum diameter of the previous coins, and ‘CURRENT’ is the index of the current coin.
There will be two types of recursive calls: first, in which we will consider picking the current coin and second, in which we drop the current coin.
The steps are as follows: