Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Print the Longest Increasing Subsequence

MEDIUMProblemSolveExternal Links

Description

You are given an array of integers arr[] of size n. Your task is to find and return the Longest Increasing Subsequence (LIS) of the given array.

A subsequence is a sequence derived from the array by deleting zero or more elements without changing the relative order of the remaining elements. An increasing subsequence is one where each element is strictly greater than the one before it.

Among all increasing subsequences, you must return the one with the maximum length. If multiple LIS of the same maximum length exist, return the one that appears first based on the lexicographical order of their indices (i.e., the earliest combination of positions from the original sequence).

Unlike the simpler version of this problem that only asks for the length of the LIS, this variant requires you to print the actual elements that form the subsequence.

Examples

Example 1

Input: arr = [10, 20, 3, 40]

Output: [10, 20, 40]

Explanation: All increasing subsequences of this array are: [10], [20], [3], [40], [10, 20], [10, 40], [20, 40], [3, 40], and [10, 20, 40]. Among these, [10, 20, 40] is the longest with length 3. No other increasing subsequence has length 3 or more, so we return [10, 20, 40].

Example 2

Input: arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]

Output: [10, 22, 33, 50, 60, 80]

Explanation: There are multiple longest increasing subsequences of length 6, for example [10, 22, 33, 50, 60, 80] and [10, 22, 33, 41, 60, 80]. We return [10, 22, 33, 50, 60, 80] because at the first position where the two differ (index 3 in the subsequence), 50 appears at index 5 in the original array while 41 appears at index 6 — the first subsequence uses the earlier index, making it lexicographically smaller by index.

Example 3

Input: arr = [5, 4, 3, 2, 1]

Output: [5]

Explanation: The array is strictly decreasing — no element has a larger element after it. Every element alone is an increasing subsequence of length 1. The first such element is 5, so we return [5].

Constraints

  • 1 ≤ n ≤ 5 × 10³
  • 0 ≤ arr[i] ≤ 10⁹

Editorial

Brute Force

Intuition

The most direct way to find the longest increasing subsequence is to simply generate every possible subsequence of the array, check whether each one is strictly increasing, and keep track of the longest one found.

Imagine you have a collection of numbered cards laid out in a row. You want to pick some cards (keeping their left-to-right order) such that the numbers on the picked cards form a strictly increasing sequence, and you want to pick as many cards as possible. The brute force approach is to literally try every combination of cards: pick no cards, pick just card 1, pick just card 2, pick cards 1 and 2 together, pick cards 1 and 3, and so on.

We can implement this using recursion with backtracking. At each element, we make a choice: include it in our current subsequence (if it maintains the increasing property) or skip it. We explore both choices recursively and track the longest valid subsequence found.

Step-by-Step Explanation

Let's trace through with arr = [10, 20, 3, 40]:

Step 1: Start with an empty subsequence. Begin exploring from index 0.

  • current = [], last_element = -∞, best_result = []

Step 2: Consider arr[0] = 10. Since 10 > -∞, we can include it.

  • Include 10 → current = [10]. Explore from index 1.
  • Decision: Try including 10 first.

Step 3: With current = [10], consider arr[1] = 20. Since 20 > 10, we can include it.

  • Include 20 → current = [10, 20]. Explore from index 2.

Step 4: With current = [10, 20], consider arr[2] = 3. Since 3 < 20, we cannot include it (would break the increasing property).

  • Skip 3. Move to index 3.

Step 5: With current = [10, 20], consider arr[3] = 40. Since 40 > 20, include it.

  • current = [10, 20, 40]. No more elements. Save this — length 3 is our best so far.
  • best_result = [10, 20, 40]

Step 6: Backtrack: remove 40, remove 20. Try skipping arr[1] = 20.

  • current = [10]. Consider arr[2] = 3. Since 3 < 10, skip.

Step 7: With current = [10], consider arr[3] = 40. Since 40 > 10, include it.

  • current = [10, 40]. Length 2 < best 3. Not an improvement.

Step 8: Backtrack further: remove 10. Try starting without arr[0].

  • Explore subsequences starting from arr[1] = 20: [20], [20, 40] (length 2).
  • Explore subsequences starting from arr[2] = 3: [3], [3, 40] (length 2).
  • Explore subsequences starting from arr[3] = 40: [40] (length 1).

Step 9: None of these beat the best of length 3.

Step 10: After exploring all 2⁴ = 16 possible inclusion/exclusion combinations, the longest increasing subsequence is [10, 20, 40] with length 3.

Final Result: [10, 20, 40]

Algorithm

  1. Maintain a global result list to track the longest increasing subsequence found so far
  2. Define a recursive function solve(index, current):
    • If current is longer than result, update result
    • For each index i from index to n-1:
      • If current is empty OR arr[i] is greater than the last element of current:
        • Add arr[i] to current
        • Recursively call solve(i + 1, current)
        • Remove arr[i] from current (backtrack)
  3. Call solve(0, []) and return result

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> result;

    void solve(vector<int>& arr, int n, int index, vector<int>& current) {
        if (current.size() > result.size()) {
            result = current;
        }
        for (int i = index; i < n; i++) {
            if (current.empty() || arr[i] > current.back()) {
                current.push_back(arr[i]);
                solve(arr, n, i + 1, current);
                current.pop_back();
            }
        }
    }

    vector<int> longestIncreasingSubsequence(int n, vector<int>& arr) {
        result.clear();
        vector<int> current;
        solve(arr, n, 0, current);
        return result;
    }
};
class Solution:
    def longestIncreasingSubsequence(self, n, arr):
        result = []

        def solve(index, current):
            nonlocal result
            if len(current) > len(result):
                result = current[:]
            for i in range(index, n):
                if not current or arr[i] > current[-1]:
                    current.append(arr[i])
                    solve(i + 1, current)
                    current.pop()

        solve(0, [])
        return result
import java.util.*;

class Solution {
    private List<Integer> result = new ArrayList<>();

    public List<Integer> longestIncreasingSubsequence(int n, int[] arr) {
        result.clear();
        solve(arr, n, 0, new ArrayList<>());
        return result;
    }

    private void solve(int[] arr, int n, int index, List<Integer> current) {
        if (current.size() > result.size()) {
            result = new ArrayList<>(current);
        }
        for (int i = index; i < n; i++) {
            if (current.isEmpty() || arr[i] > current.get(current.size() - 1)) {
                current.add(arr[i]);
                solve(arr, n, i + 1, current);
                current.remove(current.size() - 1);
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(2ⁿ)

At each element, we make two choices — include it or skip it. This creates a binary decision tree with up to 2ⁿ leaves. For each leaf (a complete subsequence), we also spend O(n) copying it when it becomes the new best. In the worst case, the total time is O(n × 2ⁿ).

Space Complexity: O(n)

The recursion stack can go at most n levels deep (one level per element). The current subsequence also holds at most n elements. So the auxiliary space is O(n), not counting the output.

Why This Approach Is Not Efficient

The brute force explores all 2ⁿ possible subsequences. With n up to 5,000, that means up to 2⁵⁰⁰⁰ operations — a number so astronomically large that no computer could ever finish it.

The root cause is redundant computation. Consider two different paths in the recursion that both arrive at index i with the same "last included element." Both will explore the exact same future choices, doing identical work twice. For example, if we reach index 5 with last element 20 via the path [10, 20] and also via the path [15, 20], the remaining exploration from index 5 onward is identical in both cases.

This overlapping subproblem structure is a classic signal that Dynamic Programming can eliminate the redundancy. Instead of re-exploring the same states, we can store results and reuse them.

Bar chart comparing exponential brute force time versus quadratic DP time for n=5000
Bar chart comparing exponential brute force time versus quadratic DP time for n=5000

Better Approach - Dynamic Programming

Intuition

Instead of generating every subsequence, we can build the answer bottom-up by asking a simpler question for each position: What is the length of the longest increasing subsequence that ends exactly at this index?

Imagine lining up dominoes in a row. For each domino, you look back at all previous dominoes and ask: "Which of these earlier dominoes can I place right before me to form the longest chain?" You pick the one that gives you the longest chain so far, then add yourself to the end.

We create an array dp where dp[i] stores the length of the longest increasing subsequence ending at index i. For each element arr[i], we look at every previous element arr[j] (where j < i). If arr[i] > arr[j], then we could extend the LIS ending at j by one more element — so dp[i] = max(dp[i], dp[j] + 1).

After filling the entire dp array, the maximum value in it gives us the LIS length. However, this approach has a critical limitation: it tells us the length of the LIS but does not directly tell us which elements form it.

Step-by-Step Explanation

Let's trace through with arr = [10, 20, 3, 40]:

Step 1: Initialize dp = [1, 1, 1, 1]. Every element alone is an increasing subsequence of length 1.

Step 2: Process i=1 (arr[1]=20). Check j=0: arr[0]=10. Is 20 > 10? Yes. dp[0]+1 = 2 > dp[1] = 1, so update dp[1] = 2.

  • dp = [1, 2, 1, 1]. LIS ending at index 1 has length 2 (sequence: 10 → 20).

Step 3: Process i=2 (arr[2]=3). Check j=0: arr[0]=10. Is 3 > 10? No, skip.

Step 4: Still i=2. Check j=1: arr[1]=20. Is 3 > 20? No, skip. dp[2] stays 1.

  • dp = [1, 2, 1, 1]. Element 3 cannot extend any previous LIS.

Step 5: Process i=3 (arr[3]=40). Check j=0: arr[0]=10. Is 40 > 10? Yes. dp[0]+1 = 2 > dp[3] = 1, so update dp[3] = 2.

  • dp = [1, 2, 1, 2]. Current best LIS ending at 3 is length 2.

Step 6: Still i=3. Check j=1: arr[1]=20. Is 40 > 20? Yes. dp[1]+1 = 3 > dp[3] = 2, so update dp[3] = 3.

  • dp = [1, 2, 1, 3]. Found a longer chain: 10 → 20 → 40.

Step 7: Still i=3. Check j=2: arr[2]=3. Is 40 > 3? Yes. But dp[2]+1 = 2 ≤ dp[3] = 3. No improvement.

  • dp = [1, 2, 1, 3]. Final dp array.

Step 8: The maximum value in dp is 3 (at index 3). The LIS has length 3.

Result: LIS length = 3. But we only know the length — we cannot determine which specific elements form this subsequence from the dp array alone.

DP Table Filling — Computing LIS Length — Watch how we fill the dp array by comparing each element with all previous elements, building up LIS lengths from left to right.

Algorithm

  1. Create a dp array of size n, initialized to all 1s (each element is a subsequence of length 1)
  2. For each index i from 1 to n-1:
    • For each index j from 0 to i-1:
      • If arr[i] > arr[j] (maintaining increasing order):
        • Update dp[i] = max(dp[i], dp[j] + 1)
  3. Return the maximum value in the dp array

Note: This only returns the LIS length, not the actual elements.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    // Returns only the LENGTH of the LIS, not the subsequence itself
    int longestIncreasingSubsequenceLength(int n, vector<int>& arr) {
        vector<int> dp(n, 1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }

        return *max_element(dp.begin(), dp.end());
    }
};
class Solution:
    # Returns only the LENGTH of the LIS, not the subsequence itself
    def longestIncreasingSubsequenceLength(self, n, arr):
        dp = [1] * n

        for i in range(1, n):
            for j in range(i):
                if arr[i] > arr[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)
import java.util.*;

class Solution {
    // Returns only the LENGTH of the LIS, not the subsequence itself
    public int longestIncreasingSubsequenceLength(int n, int[] arr) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int maxLen = 0;
        for (int val : dp) {
            maxLen = Math.max(maxLen, val);
        }
        return maxLen;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times, and for each index i, the inner loop checks all indices j from 0 to i-1. Total comparisons: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2, which is O(n²). With n ≤ 5,000, that is roughly 12.5 million operations — well within time limits.

Space Complexity: O(n)

We store a single dp array of size n. No additional data structures grow with the input.

Why This Approach Is Not Efficient

The DP approach dramatically reduces time complexity from O(2ⁿ) to O(n²), making it fast enough for the given constraints. However, it has a critical shortcoming for this particular problem: it only computes the LIS length, not the actual subsequence.

Knowing that the answer is "length 3" is not enough — the problem requires us to output the specific elements [10, 20, 40]. The dp array alone tells us that the longest subsequence ending at index 3 has length 3, but it does not record which previous elements were part of that chain.

To reconstruct the actual subsequence, we need to remember the path through which each dp value was built. Specifically, when we update dp[i] = dp[j] + 1, we should also record that "index j is the predecessor of index i in the LIS." This is exactly what the next approach introduces: a parent array that stores these predecessor relationships, allowing us to backtrack from the end of the LIS to its beginning.

Optimal Approach - DP with Parent Backtracking

Intuition

We already know how to find the LIS length using DP. The missing piece is reconstruction — figuring out which elements actually form the longest chain.

Think of it like finding the longest chain of people in a relay race. The DP approach tells you the race has 3 legs (length 3), but not who ran each leg. If each runner remembers who handed them the baton (their predecessor), you can trace back from the final runner to reconstruct the entire relay team.

We introduce a parent array alongside the dp array. parent[i] stores the index of the element that comes immediately before arr[i] in the LIS ending at index i. Initially, parent[i] = i (each element is its own predecessor, meaning it starts a new chain).

Whenever we update dp[i] = dp[j] + 1, we also set parent[i] = j — recording that the LIS ending at i was extended from the LIS ending at j.

After filling both arrays, we find the index with the maximum dp value, then follow the parent pointers backward to collect the entire subsequence. Finally, we reverse the collected elements (since we traced backward) to get the LIS in correct order.

Step-by-Step Explanation

Let's trace through with arr = [10, 20, 3, 40]:

Step 1: Initialize dp = [1, 1, 1, 1] and parent = [0, 1, 2, 3]. Each element starts as its own chain of length 1.

Step 2: Process i=1 (arr[1]=20). Check j=0: 20 > 10 and dp[0]+1 = 2 > dp[1] = 1. Update dp[1] = 2, parent[1] = 0.

  • dp = [1, 2, 1, 1], parent = [0, 0, 2, 3]. The LIS ending at index 1 came from index 0.

Step 3: Process i=2 (arr[2]=3). Check j=0: 3 < 10, skip. Check j=1: 3 < 20, skip. No updates.

  • dp = [1, 2, 1, 1], parent = [0, 0, 2, 3]. Element 3 starts its own chain.

Step 4: Process i=3 (arr[3]=40). Check j=0: 40 > 10, dp[0]+1 = 2 > 1. Update dp[3] = 2, parent[3] = 0.

  • dp = [1, 2, 1, 2], parent = [0, 0, 2, 0].

Step 5: Still i=3. Check j=1: 40 > 20, dp[1]+1 = 3 > 2. Update dp[3] = 3, parent[3] = 1.

  • dp = [1, 2, 1, 3], parent = [0, 0, 2, 1]. Found a longer chain through index 1.

Step 6: Still i=3. Check j=2: 40 > 3, dp[2]+1 = 2 ≤ 3. No improvement.

  • dp = [1, 2, 1, 3], parent = [0, 0, 2, 1]. DP filling complete.

Step 7: Find maximum: dp[3] = 3 is the largest. Start backtracking from index 3.

Step 8: Backtrack: index 3 → arr[3] = 40. Follow parent[3] = 1.

Step 9: Backtrack: index 1 → arr[1] = 20. Follow parent[1] = 0.

Step 10: Backtrack: index 0 → arr[0] = 10. parent[0] = 0 (self-reference). Stop.

Step 11: Collected in reverse: [40, 20, 10]. Reverse to get [10, 20, 40].

Result: [10, 20, 40]

DP with Parent Array — Build and Backtrack — Watch how we fill both dp and parent arrays simultaneously, then backtrack through parent pointers to reconstruct the actual LIS elements.

Algorithm

  1. Create two arrays of size n:
    • dp[i] = 1 for all i (length of LIS ending at index i)
    • parent[i] = i for all i (predecessor index, self means no predecessor)
  2. For each index i from 1 to n-1:
    • For each index j from 0 to i-1:
      • If arr[i] > arr[j] AND dp[j] + 1 > dp[i]:
        • Update dp[i] = dp[j] + 1
        • Update parent[i] = j (record the predecessor)
  3. Find max_idx = index of the maximum value in dp
  4. Backtrack from max_idx using parent pointers:
    • Collect arr[idx], then move to parent[idx]
    • Stop when parent[idx] == idx (reached the start of the chain)
  5. Reverse the collected elements and return

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> longestIncreasingSubsequence(int n, vector<int>& arr) {
        vector<int> dp(n, 1);
        vector<int> parent(n);
        for (int i = 0; i < n; i++) parent[i] = i;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
        }

        int maxIdx = 0;
        for (int i = 1; i < n; i++) {
            if (dp[i] > dp[maxIdx]) maxIdx = i;
        }

        vector<int> lis;
        int idx = maxIdx;
        while (parent[idx] != idx) {
            lis.push_back(arr[idx]);
            idx = parent[idx];
        }
        lis.push_back(arr[idx]);
        reverse(lis.begin(), lis.end());
        return lis;
    }
};
class Solution:
    def longestIncreasingSubsequence(self, n, arr):
        dp = [1] * n
        parent = list(range(n))

        for i in range(1, n):
            for j in range(i):
                if arr[i] > arr[j] and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    parent[i] = j

        max_idx = 0
        for i in range(1, n):
            if dp[i] > dp[max_idx]:
                max_idx = i

        lis = []
        idx = max_idx
        while parent[idx] != idx:
            lis.append(arr[idx])
            idx = parent[idx]
        lis.append(arr[idx])
        return lis[::-1]
import java.util.*;

class Solution {
    public List<Integer> longestIncreasingSubsequence(int n, int[] arr) {
        int[] dp = new int[n];
        int[] parent = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) parent[i] = i;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
        }

        int maxIdx = 0;
        for (int i = 1; i < n; i++) {
            if (dp[i] > dp[maxIdx]) maxIdx = i;
        }

        List<Integer> lis = new ArrayList<>();
        int idx = maxIdx;
        while (parent[idx] != idx) {
            lis.add(arr[idx]);
            idx = parent[idx];
        }
        lis.add(arr[idx]);
        Collections.reverse(lis);
        return lis;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The DP filling phase uses two nested loops: the outer loop runs n times, and the inner loop runs up to i times for each i. Total iterations: n(n-1)/2 = O(n²). The backtracking phase follows parent pointers at most n times, which is O(n). Overall: O(n²) + O(n) = O(n²).

With n ≤ 5,000, the total operations are roughly 12.5 million, which is efficient.

Space Complexity: O(n)

We store two arrays (dp and parent) each of size n, plus the output list of at most n elements. Total auxiliary space is O(n).