Given an integer array arr, find one longest subsequence with values appearing in strictly increasing order. A subsequence keeps the original relative order but may skip any number of elements. Return the values belonging to one maximum-length increasing subsequence. Multiple maximum-length answers may exist, and any valid answer is acceptable.
Example 1
Input: arr = [5, 1, 6, 2, 3, 4]
Output: [1, 2, 3, 4]
Explanation: The values at indices 1, 3, 4, 5 preserve the original order and form a strictly increasing subsequence of maximum length 4.
Example 2
Input: arr = [7, 7, 7]
Output: [7]
Explanation: Equal values cannot extend a strictly increasing subsequence, so every valid increasing subsequence has length 1.
Approach
Every array value can start an increasing subsequence of length 1. A later value can extend a chain only after a smaller earlier value. The best earlier chain therefore provides both a new length and a useful predecessor.
An array named dp stores the longest length ending at each position. A second array named parent stores the preceding position from the chosen chain. Following parent links from the best ending position builds the answer backward, and a final reversal restores the original order.
Algorithm
Begin with every
dpvalue set to1, because each array element forms a valid increasing subsequence without help from another position.Keep every
parentposition pointing to the same position at first, so a length-one chain has a clear stopping point during reconstruction.Process positions from left to right, because every chain ending at the current position depends only on already solved earlier positions.
Compare each current value with every earlier value, and allow an extension only after a strictly smaller value to preserve increasing order.
Store
dp[previous] + 1andpreviousafter a strict length improvement, because the longer earlier chain becomes the chosen path into the current value.Track the ending position of the largest
dpvalue, so reconstruction begins at the final value of a maximum-length chain.Follow
parentlinks into an answer list and reverse the collected values, because predecessor traversal visits the longest subsequence from end to start.
Dry Run
Print LIS
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Return one longest increasing subsequence. vector<int> longestIncreasingSubsequence(vector<int>& arr) { int n = arr.size(); // Empty input has no increasing subsequence. if (n == 0) { return {}; } // Give every value a valid length-one chain. vector<int> dp(n, 1); // Store the chosen predecessor for every position. vector<int> parent(n); // Preserve the end of the longest chain found. int longestEnd = 0; // Build chain lengths after all needed states exist. for (int current = 0; current < n; current++) { // A new chain ends at the current position. parent[current] = current; // Test every possible earlier predecessor. for (int previous = 0; previous < current; previous++) { // Extend only through a smaller earlier value. if (arr[previous] < arr[current] && dp[previous] + 1 > dp[current]) { // Save the improved chain length. dp[current] = dp[previous] + 1; // Remember the path producing the improvement. parent[current] = previous; } } // Move the endpoint only after a longer chain. if (dp[current] > dp[longestEnd]) { longestEnd = current; } } // Collect values while following predecessor links. vector<int> answer; // Stop at the self-parented start of the chain. while (parent[longestEnd] != longestEnd) { answer.push_back(arr[longestEnd]); longestEnd = parent[longestEnd]; } // Add the first value after traversal stops. answer.push_back(arr[longestEnd]); // Restore the original left-to-right order. reverse(answer.begin(), answer.end()); return answer; }};// Driver codeint main() { vector<int> arr = {5, 1, 6, 2, 3, 4}; Solution obj; vector<int> answer = obj.longestIncreasingSubsequence(arr); for (int value : answer) { cout << value << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N2), where N is the number of elements, because every position compares with all earlier positions, while reconstruction follows at most N parent links. The quadratic comparison work dominates.
Space Complexity: O(N), because the dp, parent, and reconstructed answer arrays each store at most N values.
Interview follow-up Questions
Strict inequality keeps every chosen value larger than the preceding value. A non-strict comparison would solve the longest non-decreasing subsequence variant instead.
Be the first to add a comment.