Problem Statement
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example Inputs and Outputs
-
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], with a length of 4.
-
Input: nums = [0,1,0,3,2,3]
Output: 4
-
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Constraints
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4
Approach
a. Dynamic Programming (Recursive with Memoization)
Steps
- Use a recursive function
rec(level, nums, dp) to find the LIS ending at level.
- Initialize a DP array
dp with -1 to indicate uncomputed states.
- If
level is less than 0, return 0 (base case).
- Use memoization to avoid redundant calculations.
- For each
level, check all previous elements (prev) to find valid subsequences where nums[prev] < nums[level].
- Combine the results to compute the LIS at each level and return the maximum value.
Code Snippet
Dry Run
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
- Initialize
dp = [-1, -1, -1, -1, -1, -1, -1, -1].
- Call
rec(level, nums, dp) for each index and compute LIS at that point.
- Use memoization to store results for previously computed states.
Complexity Analysis
- Time Complexity:
O(n^2) due to the nested loop for each level and prev.
- Space Complexity:
O(n) for the memoization table.
Conclusion
This guide explains how to solve the Longest Increasing Subsequence problem using recursion with memoization. The approach ensures efficiency by storing intermediate results, avoiding redundant calculations. For larger inputs, exploring more optimized solutions like the O(n log n) approach is recommended.