SPOJ NDS HELP!!

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

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

Yes! please