Problem Statement
Given an integer array nums, find the length of the longest subsequence with strictly increasing values.
A subsequence preserves the original relative order of selected values but may skip any number of positions. Equal values cannot extend a strictly increasing subsequence.
Example 1
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: One longest increasing subsequence is [2, 3, 7, 101], with length 4.
Example 2
Input: nums = [7, 7, 7, 7]
Output: 1
Explanation: Equal values cannot follow one another in a strictly increasing subsequence, so every valid choice has length 1.
Recursion
Every array position offers a small choice: skip the current value, or take the current value after a smaller selected value. Repeating the same choice for the remaining suffix explores every valid subsequence without changing original order.
The state solve(index, previousIndex) stores the best length available from index onward after previousIndex was selected. A value of -1 means no earlier value has been selected, so the first call starts at solve(0, -1).
Algorithm
Begin at
index = 0withpreviousIndex = -1, so the complete array remains available and no previous value restricts the first selection.Stop at
index = nand return0, because no array value remains to increase the subsequence length.Explore the skip branch with the same
previousIndex, so the current value is ignored without changing the last selected value.Allow the take branch only after no earlier selection or a strictly smaller previous value, so every accepted pair preserves strict increase.
Add
1to the take branch and movepreviousIndextoindex, because the selected value becomes the new ending value.Compare the take and skip lengths, so the longer valid subsequence is preserved for the current state.
Return the result from
solve(0, -1), because the initial state represents every valid subsequence of the full array.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Finds the best length from the current position. int solve(int index, int previousIndex, vector<int>& nums) { int n = nums.size(); // No values remain after the final position. if (index == n) { return 0; } // Skipping keeps the earlier ending value. int notTake = solve(index + 1, previousIndex, nums); int take = 0; // A larger value can extend the sequence. if (previousIndex == -1 || nums[index] > nums[previousIndex]) { // Taking changes the selected ending index. take = 1 + solve(index + 1, index, nums); } // The longer branch gives the best valid length. return max(take, notTake); }public: // Returns the longest increasing subsequence length. int lengthOfLIS(vector<int>& nums) { // The starting state has no earlier selection. return solve(0, -1, nums); }};// Driver codeint main() { vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18}; Solution obj; cout << obj.lengthOfLIS(nums) << endl; return 0;}Complexity Analysis
Time Complexity: O(2N), where N is the number of array positions, because every position can create a take branch and a skip branch across a recursion depth of N.
Space Complexity: O(N), because the deepest recursive path stores at most one call for every array position.
Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.
Memoization
Different take-or-skip paths can reach the same pair of index and previousIndex. Recomputing an identical suffix choice wastes time because the best remaining length depends only on the state pair.
A two-dimensional dp table stores every completed state. The shifted column previousIndex + 1 maps sentinel -1 to column 0, allowing normal array indexing while preserving the recursive state and choices.
Algorithm
Begin with the same state
solve(0, -1), so memoization preserves the recursive meaning and the complete search space.Create a
dptable withnrows andn + 1columns filled with-1, so every untouched cell marks an uncalculated state.Stop at
index = nwith length0, because no suffix value remains for either branch.Reuse
dp[index][previousIndex + 1]after a stored value appears, so repeated suffix choices avoid another recursive search.Calculate the skip branch with an unchanged previous index, so the current value can be safely ignored.
Calculate the take branch only after a strict increase, so invalid equal or decreasing pairs never enter the subsequence.
Store the larger branch length in the shifted
dpcell, so every later visit receives the complete answer immediately.Return the value produced by the initial state, because the starting pair represents the full problem.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Finds and stores the best remaining length. int solve( int index, int previousIndex, vector<int>& nums, vector<vector<int>>& dp ) { int n = nums.size(); // No values remain after the final position. if (index == n) { return 0; } int previousColumn = previousIndex + 1; // A stored state avoids repeated suffix work. if (dp[index][previousColumn] != -1) { return dp[index][previousColumn]; } // Skipping keeps the earlier ending value. int notTake = solve( index + 1, previousIndex, nums, dp ); int take = 0; // A larger value can extend the sequence. if (previousIndex == -1 || nums[index] > nums[previousIndex]) { // Taking changes the selected ending index. take = 1 + solve(index + 1, index, nums, dp); } // Store the longer result for later visits. dp[index][previousColumn] = max(take, notTake); return dp[index][previousColumn]; }public: // Returns the longest increasing subsequence length. int lengthOfLIS(vector<int>& nums) { int n = nums.size(); // A shifted column represents previous index -1. vector<vector<int>> dp( n, vector<int>(n + 1, -1) ); // The starting state has no earlier selection. return solve(0, -1, nums, dp); }};// Driver codeint main() { vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18}; Solution obj; cout << obj.lengthOfLIS(nums) << endl; return 0;}Complexity Analysis
Time Complexity: O(N2), where N is the number of positions, because at most N × (N + 1) state pairs are calculated once with constant work per state.
Space Complexity: O(N2 + N), because the dp table stores quadratic state data and the recursion stack can contain at most N calls.
Tabulation
Memoization starts from the full state and discovers smaller states through recursive calls. Tabulation reverses the direction: an extra zero row represents the exhausted suffix, and earlier array positions are filled from already completed later rows.
For a fixed index, only previous positions from -1 through index - 1 are meaningful. The same skip and take choices now read from row index + 1, so recursion stack space disappears without changing the state definition.
Algorithm
Create a
dptable withn + 1rows andn + 1columns filled with0, so rowndirectly represents the exhausted suffix.Move
indexfromn - 1down to0, so every transition can read the already completed row forindex + 1.Visit
previousIndexfromindex - 1down to-1, so only valid earlier selections and the no-selection sentinel receive states.Read the skip length from
dp[index + 1][previousIndex + 1], so skipping preserves the earlier selected ending value.Read the take length from
1 + dp[index + 1][index + 1]only after a strict increase, so the current index becomes the previous selection for the remaining suffix.Store the larger branch in
dp[index][previousIndex + 1], so the current state matches the recursive result.Return
dp[0][0], because row0and shifted column0represent the full array with no earlier selection.
Dry Run
Longest Increasing Subsequence Tabulation
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the longest increasing subsequence length. int lengthOfLIS(vector<int>& nums) { int n = nums.size(); // Row n represents the exhausted suffix. vector<vector<int>> dp( n + 1, vector<int>(n + 1, 0) ); // Backward order keeps the next row ready. for (int index = n - 1; index >= 0; index--) { // Only earlier positions form valid states. for ( int previousIndex = index - 1; previousIndex >= -1; previousIndex-- ) { // Skipping keeps the earlier ending value. int notTake = dp[index + 1][previousIndex + 1]; int take = 0; // A larger value can extend the sequence. if ( previousIndex == -1 || nums[index] > nums[previousIndex] ) { // Taking changes the selected ending index. take = 1 + dp[index + 1][index + 1]; } // Store the longer result for the state. dp[index][previousIndex + 1] = max(take, notTake); } } // Shifted column zero means no earlier selection. return dp[0][0]; }};// Driver codeint main() { vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18}; Solution obj; cout << obj.lengthOfLIS(nums) << endl; return 0;}Complexity Analysis
Time Complexity: O(N2), where N is the number of positions, because the nested state loops evaluate every valid pair of current and previous positions once.
Space Complexity: O(N2), because the iterative dp table stores every suffix and shifted previous-index state without recursion stack space.
Space Optimization
Every tabulation transition reads only row index + 1. Rows farther ahead never appear again, so a nextRow array can preserve the needed suffix answers while a currentRow array builds the current states.
After every current row is complete, the current row becomes the next row for the following earlier index. Performing the shift after all previous-index states are calculated prevents partially updated values from corrupting transitions.
Algorithm
Create
nextRowwithn + 1zeros, so the initial rolling row represents the exhausted suffix.Move
indexfromn - 1down to0, so the retained row always belongs to suffix positionindex + 1.Create a zero-filled
currentRowfor each index, so stale states from a later iteration cannot enter the current calculation.Read the skip length from
nextRow[previousIndex + 1], so the previous selected value remains unchanged.Read the take length from
1 + nextRow[index + 1]only after a strict increase, so selection changes the ending index exactly like the full table.Store the larger choice in
currentRow[previousIndex + 1], so every current state preserves the recursive maximum.Shift
currentRowintonextRowonly after the row is complete, so all transitions for one index read the same untouched suffix row.Return
nextRow[0], because the final rolling row represents index0with no earlier selection.
Dry Run
Longest Increasing Subsequence Space Optimization
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the longest increasing subsequence length. int lengthOfLIS(vector<int>& nums) { int n = nums.size(); // The next row starts as the exhausted suffix. vector<int> nextRow(n + 1, 0); // Backward order keeps the needed suffix row ready. for (int index = n - 1; index >= 0; index--) { // A fresh row prevents stale current states. vector<int> currentRow(n + 1, 0); // Only earlier positions form valid states. for ( int previousIndex = index - 1; previousIndex >= -1; previousIndex-- ) { // Skipping keeps the earlier ending value. int notTake = nextRow[previousIndex + 1]; int take = 0; // A larger value can extend the sequence. if ( previousIndex == -1 || nums[index] > nums[previousIndex] ) { // Taking changes the selected ending index. take = 1 + nextRow[index + 1]; } // Calculate the current state from both choices. currentRow[previousIndex + 1] = max(take, notTake); } // Shift the current row after every state is ready. nextRow.swap(currentRow); } // Shifted column zero means no earlier selection. return nextRow[0]; }};// Driver codeint main() { vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18}; Solution obj; cout << obj.lengthOfLIS(nums) << endl; return 0;}Complexity Analysis
Time Complexity: O(N2), where N is the number of state positions, because the same quadratic set of state pairs is evaluated once using two rolling rows.
Space Complexity: O(N), because nextRow and currentRow each store only N + 1 state values.
Interview follow-up Questions
No. Selected positions must preserve original order, but gaps between selected positions are allowed.
Be the first to add a comment.