leetCode Question: Longest Increasing Subsequence

Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Analysis:

The simple but relatively slow solution is classic DP (dynamic programming) approach. For now, I will analyze this solution in detail and breifly introduce the n log n algorithm.

For each index i in the array nums, we could have an array res to store the length of longest increasing subsequence from nums[ 0 ] to nums[ i ]. For index i, we have multiple numbers from nums[ 0 ] to nums[ i-1 ], also, we have multiple results from res[ 0 ] to res[ i ]. Denote j is index from 0 to i-1, for each possible j, if nums[ i ] > nums[ j ] (current number > one previous number), it means the longest increasing subsequence that ends at num[ j ] + num[ i ] is a valid increasing subsequence, and the length of it is res[ j ] + 1. So if we got the longest length of all possible j (from 0 to i-1), it should be the longest length in current index i. The outer loop for i is just the scan the whole nums array from the begining to the end. In the end, the maximum value in array res, is the final longest length we want.

In the figure above, blue color means the data array (green font mean the actural longest increading subseuqnce), red color means the result array storing the longest length.

In the above solution, everytime we have to look back and check from 0 to current index - 1 for updating the current index. This look back part is most time consuming. So for the n log( n ) algorithm, we have to modify the look back part. Instead of looking back, we could have a new array s, s[ i ] stores the minimum A[i] when the len of longest increaing seq is d[ i ]. It is not hard to observe array s is ordered. Then, for each nums [ i ], we search the array s[ i ], to find the index j where s[ j ] is less than but closest to nums[ i ]. The index j is then the result.

Code (C++) (Simple DP):

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

if (nums.size()==0){return 0;}

int res_max = 1;

vector<int> res(nums.size(), 1);

for (int i=1;i< nums.size();i++){

for (int j = 0; j < i; j++){

if (nums[i] > nums[j]){

res[i] = max(res[i], res[j] + 1);

}

}

//cout << res[i] << ", ";

res_max = max(l, res[i]);

}

return res_max;

}

};

Code (Python) (Simple DP):

class Solution(object):

def lengthOfLIS(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

if len(nums) == 0:

return 0

res_max = 1

res = [1]*len(nums)

for i in range(len(nums)):

for j in range(0,i):

if nums[i] > nums[j]:

res[i] = max(res[j]+1, res[i])

res_max = max(res_max, res[i])

return res_max