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?
This approach uses dynamic programming to solve the problem in O(n^2) time complexity. We maintain a dp array where dp[i] represents the length of the longest increasing subsequence that ends with nums[i]. For each element, we iterate over all previous elements to see if they can be included in the subsequence ending at the current element, and update dp[i] accordingly.
The code initializes a dp array to store the length of the longest subsequence ending at each index. The outer loop considers each element, and the inner loop checks against elements before the current one to update the dp array. Finally, the maximum length found in the dp array is returned as the result.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) where n is the length of the input array. Space Complexity: O(n) for storing the dp array.
In this approach, we use a combination of dynamic programming and binary search to solve the problem in O(n log n) time. This is often called the 'patience sorting' technique where we maintain a list, 'ends', to store the smallest ending value of any increasing subsequence with length i+1 in 'ends[i]'. We use binary search to find the position where each element in nums can be placed in 'ends'.
This C solution uses a lowerBound function which acts similarly to std::lower_bound in C++. It finds the position to insert (or replace) each element of nums in the 'ends' list, effectively forming the required subsequences.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n). Space Complexity: O(n).
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2) where n is the length of the input array. Space Complexity: O(n) for storing the dp array. |
| Optimized DP with Binary Search (Patience Sorting) | Time Complexity: O(n log n). Space Complexity: O(n). |
Longest Increasing Subsequence • Tushar Roy - Coding Made Simple • 454,864 views views
Watch 9 more video solutions →Practice Longest Increasing Subsequence with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor