Longest Increasing Subsequence

lelouch · August 20, 2012, 8:12pm

I use the programming language; Python

I implemented a solution that can run in O(n^2logk) where k is the length of the LIS, and n is the length of the sequence, however I get TLE. So I broke down my solution and submitted the algorithm for LIS which runs O(nlogk), yet I still get TLE.

Can anyone explain a faster method or is it because python is too slow?

gamabunta · August 21, 2012, 4:34am

A lot of the accepted solutions have complexity O(n log k).

It might be that the time limit for python submissions scales unfavorably against python.

lelouch · August 21, 2012, 5:13am

ty, I think so too