Longest Increasing Subsequence

24
0

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 = 0 with previousIndex = -1, so the complete array remains available and no previous value restricts the first selection.

  • Stop at index = n and return 0, 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 1 to the take branch and move previousIndex to index, 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
1 / 2

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 code
int 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 dp table with n rows and n + 1 columns filled with -1, so every untouched cell marks an uncalculated state.

  • Stop at index = n with length 0, 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 dp cell, 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
1 / 3

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 code
int 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 dp table with n + 1 rows and n + 1 columns filled with 0, so row n directly represents the exhausted suffix.

  • Move index from n - 1 down to 0, so every transition can read the already completed row for index + 1.

  • Visit previousIndex from index - 1 down 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 row 0 and shifted column 0 represent the full array with no earlier selection.

Dry Run

Longest Increasing Subsequence Tabulation

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 code
int 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 nextRow with n + 1 zeros, so the initial rolling row represents the exhausted suffix.

  • Move index from n - 1 down to 0, so the retained row always belongs to suffix position index + 1.

  • Create a zero-filled currentRow for 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 currentRow into nextRow only 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 index 0 with no earlier selection.

Dry Run

Longest Increasing Subsequence Space Optimization

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 code
int 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.

Dynamic Programming

Read Similar Blogs

Comments0