MediumLeetCode #300Dynamic Programming
Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Constraints
1 <= nums.length <= 2500, -10^4 <= nums[i] <= 10^4
Examples
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
[2,3,7,101]
Solution Approach
DP where dp[i] = longest subsequence ending at i. Check all previous elements.
Implementation
def longestIncreasingSubsequence(nums):
n = len(nums)
if n == 0:
return 0
dp = [1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)Complexity Analysis
Time Complexity
O(n log n)Space Complexity
O(n)Complexity
Time:O(n log n)
Space:O(n)
Hints
- 1.Think about what makes a good subsequence
- 2.For O(n²): dp[i] = longest ending at i
- 3.For O(n log n): maintain smallest tail for each length
Asked at
Google