Can anyone suggest a DP solution for this problem?

general
1

The problem is given here- http://opc.iarcs.org.in/index.php/problems/BOOKSORT

1 Like
2

The problem is essentially asking for the longest increasing subsequence of the given sequence. The accepted answer here talks about how to solve this, first in O(N^2), then in O(NlogN). For the given constraints, the O(NlogN) solution is required.

1 Like
3

Oh damn! Now I see it. Thanx.

1 Like