New update is available. Click here to update.

Last Updated: 7 Mar, 2021

Moderate

```
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][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.
```

```
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][0] and ARR[i][1] <= 10^5
Time limit: 1 sec
```

Approaches

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:**

- 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'.

- 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).

The basic idea of this approach is to compute the LIS(Longest Increasing Subsequence) for the starting βiβ coins and by using this result compute LIS for the starting βiβ + 1 coins.

Reference: https://cpalgorithms.com/sequences/longest_increasing_subsequence.html

**The steps are as follows:**

- Sort the vector so that all the coins become arranged in the increasing order of their width.
- Create a vector βLISβ to store LISs and for the first index set LIS 1 because the first coin in the βARRβ will always have LIS as 1.
- Iterate through the 'ARR' from 1 to βNβ. (say, iterator = βiβ)
- Make LIS[ i ] = 1
- Iterate again through βARRβ from 0 to βiβ. (say, iterator = βjβ)
- If found a coin with less diameter than the coin at βiβ and its LIS in βLISβ + 1 is also greater than LIS[ i ] then set LIS[ i ] to LIS[ j ] + 1.

- Return the maximum value stored in βLISβ.

The basic idea of this approach is to store the tail (or last and the least) element of the LIS of lengths 1, 2, 3, and so on. Whenever we found a new element that is greater than the last filled element in the βTAILβ array then just append this to the array because it increases the previous longest length of LIS. Otherwise, replace this element with the element just greater than this in the already picked element ( in the βTAILβ array).

**The steps are as follows:**

- Sort the vector so that all the coins become arranged in the increasing order of their width.
- Create a vector βTAILβ to store the least possible element which makes the LIS of length βiβ + 1 where βiβ is the index in the βTAILβ array.
- Append the first element in the βTAILβ as it is because it is the only element that just makes the length of the longest LIS equal to 1.
- Iterate through the βARRβ from 1 to βNβ. (say, iterator = βiβ)
- If the last added element in the tail is smaller than the element at βARR[ i ][ 1 ]β then just append it into the βTAILβ array.
- Else,
- Found the lower bound of ARR[ i ][ 1 ] in the 'TAIL' and replace it with this coin.

- Return size of 'TAIL'.

Similar problems