Longest Increasing Subsequence
Problem Description
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?
Solve it on LeetCode
Approaches
1. Dynamic Programming
Intuition:
The idea is to use a dynamic programming table to keep track of the length of the longest increasing subsequence that ends with the element at each position in the array. At each element, we consider all previous elements and find the longest subsequence that this element can extend.
Steps:
- Initialize a
dparray wheredp[i]represents the length of the longest increasing subsequence that ends at indexi. - Iterate over each element in the array. For each element, check all previous elements:
- If the current element is greater than the previous element, then it can extend the subsequence ending at that previous element.
- Update
dp[i]to be the maximum of its current value ordp[j] + 1wherejis an index beforei. - The answer is the maximum value in the
dparray.
Code:
- Time Complexity: O(n^2), where n is the length of the array. We examine each pair of indices once.
- Space Complexity: O(n), used for the dp array.
2. Dynamic Programming with Binary Search
Intuition:
Instead of maintaining an array to find the longest increasing subsequence with a direct comparison which results in O(n^2) complexity, we can use a clever trick involving binary search. The approach is to maintain an array that keeps the "minimal" possible tail for all increasing subsequences of various lengths. This makes the time complexity significantly better.
Steps:
- Create an array
tailswheretails[i]represents the smallest tail value of all increasing subsequences of lengthi+1. - For each number in the input array:
- Use binary search (or manual iteration) to find the location it can replace in the
tailsarray. - Update the
tailsarray: if the number is larger than the largest element intails, append it. - The length of
tailswill be the length of the longest increasing subsequence.
Code:
- Time Complexity: O(n log n), due to binary searching within tails for each of the n elements.
- Space Complexity: O(n), used for the tails array.