Algorithm: Longest Increasing Subsequence

When designing a test case this week, I ran into a problem that related to the length of the “longest increasing subsequence” problem. This is a classical problem in ACM, and there are tons of blog articles and stackoverflow questions about this subject. Most of them are really hard to get, but I’m trying to organize the thought in my own words here.

What’s “Longest Increasing Subsequence” (LIS)?

For example, given an unsorted array:

nums = [7,5,3,6,1,9,12]


The LIS is [5,6,9,12], therefore the length of LIS is 4.

Thoughts?

My instinct tells me dynamic programming would be the easiest way (and the fastest way).

Let’s say we keep tracking the lengths of the LIS that ends with each number. Therefore lst[i] is the length of the longest increasing subsequence ending with nums[i]. Then,

lst[i] = max(
all lst[j] where nums[j]<nums[i], j<i
) + 1
or
1 otherwise.

result = max(lst)


Implementation

def lengthOfLIS(nums):
if not nums:
return 0
dp = [1]
for i in range(1,len(nums)):
pdp = [dp[j] for j in range(i) if nums[j]<nums[i]]+[0] # Note.
dp.append(max(pdp)+1)
return max(dp)


Note: The list was added [0] in case it it empty if the condition not satisfied.

Apparently the complexity is O(N^2), looking slow.

Enhance to O(N * log N)

In the above code, there’s comparison to all pevious numbers for every new number. This slows the algorithm.

What if we don’t compare them? Instead, we keep track of the smallest number? Here the smallest Number means:

For each number in nums, we use a list to track the LIS.

In this LIS, all the elements are as small as possible.

So the basic idea is we track an LIS-like list, and update its element as long as a smaller element arrives. If this new element has the value in the midst, just changing the value at the location. If it’s larger the all the elements in LIS, appending it to LIS.

Implementation in Python:

def lengthOfLIS(nums):
dp = []
for x in nums:
i = bisect.bisect_left(dp,x) #NOTE
if i == len(dp):
dp.append(x)
else:
dp[i] = x
return len(dp)


Note: Binary search is used in searching back the LIS, hence the complexity is O(N*log N).