0300: Longest Increasing Subsequence

Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

Input: nums = [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.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Code Solution

class Solution:
    def lengthOfLIS(self, nums):
        N = len(nums)
        
        # Maximum of below iterations:
        #     (sx + 1): [..., sx - 1] <sx> [sx + 1, ..., N - 1]
        #     (sx + 2): [..., sx - 1] <sx> [sx + 2, ..., N - 1]
        #     (sx + 3): .......................................
        # (sx + N - 1): [..., sx - 1] <sx> [sx + N, ..., N - 1]
        
        @cache
        def rec(sx):
            if sx == N:
                return 0
            cmax = 1
            for ix in range(sx + 1, N, 1):
                if nums[ix] > nums[sx]:
                    cmax = max(cmax, 1 + rec(ix))
            return cmax
        
        # Perform LIS starting from all indices:
        return max([rec(ix) for ix in range(N)])