Problem :http://www.spoj.com/problems/NDS/

Can Anyone please provide any hint regarding the solving this problem using segment trees

@vijju123

Problem :http://www.spoj.com/problems/NDS/

Can Anyone please provide any hint regarding the solving this problem using segment trees

@vijju123

Sorry, missed this post due to cook off. U still need help?

This is not a solution using segment tree, but I would just use the method of calculating the longest increasing subsequence since the algorithm for LIS makes use of these minimum last values. You can refer to the Wikipedia page for details, and the first answer by `dalex`

here is a very neat implementation.

If I think of a solution using segment trees I will update this answer

UPDATE:

You can use this approach using segment tree to calculate `dp[i]`

for each index such that `dp[i]`

is the LIS that ends at index `i`

. Then finding the answer for some `L`

should be trivial

Yes! please