LeetCode #300 Longest Increasing Subsequence

Problem

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

Example

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.

Solution1

Method: Dynamic Programming

Time Complexity: O(n^2)

Space Complexity:

class Solution:
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        
        nums = [float('-inf')] + nums
        LIS = [0 for _ in nums]
        LIS[-1] = 1
        
        for idx_i in range(len(nums) - 2, -1, -1):
            current_max_val = 1
            for idx_j in range(idx_i + 1, len(nums)):
                if nums[idx_i] < nums[idx_j]:
                    current_max_val = max(current_max_val, 1 + LIS[idx_j])
            LIS[idx_i] = current_max_val

        return LIS[0] - 1

Other Solution

https://leetcode.com/problems/longest-increasing-subsequence/discuss/152065/Python-explain-the-O(nlogn)-solution-step-by-step

Key Point

Add an infinite value at the head.