Longest Increasing Subsequence

LeetCode

LeetCode: https://leetcode.com/problems/longest-increasing-subsequence/

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

1def lengthOfLIS(nums: List[int]) -> int:
2    n = len(nums)
3    dp = [1] * n
4    
5    for i in range(n):
6        for j in range(i):
7            if nums[j] < nums[i]:
8                dp[i] = max(dp[i], dp[j] + 1)
9    
10    return max(dp)
Previous
Coin Change
1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
nums=[10, 9, 2, 5, 3, 7, 101, 18]
Step 1 / 5
Step 1:
dp[i] = length of LIS ending at i. Initialize all dp to 1.
Focus: default