Hello, This is a problem from SPOJ: http://www.spoj.pl/problems/LIS2/ My algorithm is O(nlog^2n) used 2d segment tree , but it get time limit exceeded. I think it's because the constant factor is large. Could anyone help me about how to optimize it, or is there a faster algorithm? Thanks!
Some people got accepted with O(N log^2 N), using 2D segment tree/BIT. However I didn't, so I believe they did heavy constant optimization in it.
I finally got accepted using O(N log N log M) algorithm, where N is the number of items and M is the actual LIS. You may recall O(N log M) algorithm to solve LIS (M = length of LIS), and extend it into 2D version.