Leetcode 300. Longest Increasing Subsequence (Python)

Related Topic

Dynamic-Programming.

Description

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

Sample I/O

Example 1

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

• 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?

Methodology

This question can be solved by Dynamic Programming. However there are better ways to solve this question.

We want to creat a dp list to memorize the number of increasing subsequence. If the current element is greater than prevous element, then current number of increasing subsequence is the previous number of increasing subsequence + 1. Then we return the max number in dp list

Find the base case:

Init each element of dp list to 1 as there is at least 1 number of increasing subsequence unless the input is empty list.

Find the pattern:

If the current element is greater than prevous element, then current number of increasing subsequence is the previous number of increasing subsequence + 1.

Above is the basic idea, however, you can optimazed it.

The classic dynamic programming method will compare each previous element with the current element to update the current number of increasing subsequence. However I found this is not efficent. Once the current element is greater than the max element of previous, there is no need to compare more previous elements.

Answer:

Return the max element of dp list

Code

def lengthOfLIS(self, nums: List[int]) -> int:        
        if not nums: return 0
        L = len(nums)
        dp=[1]*L
        pre_max = nums[0]
        for i in range(1,L):
            pre_max = nums[i-1] if nums[i-1]>pre_max else pre_max
            for j in range(i-1,-1,-1):
                if nums[j]<nums[i]:
                    if nums[j] == pre_max:
                        dp[i] = max(dp[i],dp[j]+1)
                        break
                    dp[i] = max(dp[i],dp[j]+1)
        return max(dp)

BigO

Create dp list will cost O(n) and iterate the dp will cost ((n-1)^2) in total will be O((n-1)^2+n)