Suppose there is an array of integers representing values of blocks. We have to create towers such that (i)th block in tower has value less than or equal to (i-1)th.

a. Calculate the height of tallest tower.

b. Calculate the minimum number of towers to equip all the blocks.

Obviously, the the answer of first part is longest decreasing array. I am not sure about second part but according to me the answer will the longest strictly increasing array.

Correct me if I am wrong.

You are correct about the first one. For the second one, you can maintain a list of integers in a set and add onto the one in the set that is greater than or equal to a[i], and erase the found integer. If no such integer exists, add that number to the set. The answer is just the size of the set. Here is an example algorithm.

a := [3, 1, 4, 6, 2]

s := binary search tree set

s = {}

is set not empty? no insert into set

s = {3}

is set not empty? yes. what number is greater than or equal to 3? 1

s = {1}

is set not empty? yes. what number is greater than or equal to 4? doesn't exist, add to set

s = {1, 4}

is set not empty? yes. what number is greater than or equal to 6? doesn't exist, add to set

s = {1, 4, 6}

is set not empty? yes, what number is greater than or equal to 2? 4.

s = {1, 2, 6}

print(s -> size)

I guess you are doing the same thing just in O(nlogn) time. Can you suggest some test in which your answer will differ from my proposed solution(LIS).

Nop.

This is a cses problem, btw.

You can test your code there.

I tried my solution and it got accepted. Thanks in between for telling about cses. What you are doing is also O(nlogn) version of lis(not dp version).