Longest Increasing Subsequence

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

Intuition

At a number, we can the longest increasing subsequence = $\max(\text{result of previous longest increasing subsequence }) + 1$

For example if we have

[2,1,2,0,4]

To find the longest increasing subsequence at 4, we can check for the longest subsequence of previous number that's smaller than 4: 2,1,2,0 to see which one has the longest subsequence

[2,1,2,0,4]
 1 1 2 1 ?

As a result, we see that at 2 we have 2 and therefore at 4 it will be 3.

So at a number we have:

• dp[i] = max(previous) + 1 if there is anything
• Else then it's dp[i] = 1 since it's the only standalone number

Implementation

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1 for _ in range(len(nums))]
        maxLength = 1

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[j] + 1, dp[i])
                    maxLength = max(dp[i], maxLength)
                
        return maxLength

Time complexity: $O(n^2)$
Space complexity: $O(n)$