Longest Increasing Subsequence

I use the programming language; Python

The problem link; http://www.codechef.com/problems/D2/

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?

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.

1 Like

ty, I think so too