New update is available. Click here to update.
Last Updated: 7 Mar, 2021
##### Kevin and the tower of coins
Moderate
Problem statement

#### Note:

``````The height of the tower is calculated by adding the width of all the coins used in the formation of this tower.
``````
##### Input Format:
``````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][0]β and βARR[i][1]β, where βARR[i][0]β is the width of the βi-thβ coin and βARR[i][1]β is the diameter of the βi-thβ coin.
``````
##### Output Format:
``````For each test case, return the maximum possible height of the tower.

Output for every test case will be printed in a separate line.
``````
##### Note:
``````You donβt need to print anything; It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 50
1 <= N <= 10^4
1 <= ARR[i][0] and ARR[i][1] <= 10^5

Time limit: 1 sec
``````
Approaches

## 01Approach

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:

1. In the 'HELPER' function
• If βCURRENTβ becomes equal to the length of 'ARR' return 0;
• Create two variables βPICKβ and βDROPβ to store the result of two recursive calls. Initialise both of them by 0.
• If the current coin has a diameter greater than 'PREVIOUS' then store the result of HELPER(ARR, ARR[CURRENT][1], CURRENT + 1) in βPICKβ and increment it by 1.
• Store the result of HELPER(ARR, PREVIOUS, CURRENT + 1) in βDROPβ.
• Return the maximum between βPICKβ and 'DROP'.
2. In the given function
• Sort the vector so that all the coins become arranged in the increasing order of their width.
• Return the result of HELPER(ARR, INT_MIN, 0).