Longest Increasing Subsequence
Given an integer array nums, return the length of the longest increasing subsequence.
Constraints:
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Examples:
Input: [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.
Solutions
Dynamic Programming
Time: O(n^2)Space: O(n)
The dynamic programming approach involves creating a dp array where dp[i] represents the length of the longest increasing subsequence ending at index i. We iterate through the array and for each element, we check all previous elements. If the current element is greater than the previous element, we update dp[i] to be the maximum of its current value and dp[j] + 1.
function lengthOfLIS(nums) {
let dp = new Array(nums.length).fill(1);
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
}
Follow-up:
What if the input array is very large and we need to find the longest increasing subsequence in real-time?
