Print Longest Increasing Subsequence

Medium20–25 min

Topics

Dynamic ProgrammingArray

Companies

AmazonMicrosoftAdobe

Given an array of integers, reconstruct one actual longest strictly increasing subsequence rather than just its length — an in-order run of elements that keeps climbing at every step. Since several different runs can tie for the longest length, ties are broken by always preferring the earliest-finishing chain, so the result stays the same no matter which language or approach produces it. The same length-only table used to compute how long the answer is can also record enough to rebuild it: whichever earlier index actually produced a given index's best length is worth remembering as that index's predecessor. Once every index has been filled in along with its predecessor, the index holding the overall best length marks the end of the answer, and walking predecessor links backward from there — either through a recursion that unwinds in the right order, or through a loop that fills a result array from its last slot toward its first — replays exactly the choices that built it, turning the stored lengths back into one concrete increasing run.

Test Case 1:

Input:nums = [11, 4, 7, 2, 9, 6, 14, 3]

Output:[4, 7, 9, 14]

Explanation:Tracing parent pointers back from the first index that reaches the maximum length (index 6, value 14) unwinds to 4, 7, 9, 14 — length 4, the longest possible here.

Test Case 2:

Input:nums = [2, 5, 2, 8, 6, 9]

Output:[2, 5, 8, 9]

Explanation:The first 2 starts the chain, 5 extends it, then 8 and the later 9 continue it — 2, 5, 8, 9 is length 4.

Test Case 3:

Input:nums = [5, 5, 5, 5, 5, 5, 5]

Output:[5]

Explanation:No element is strictly greater than an earlier one, so every chain has length 1 — the earliest index (the first 5) is returned.

Constraints

◆1 ≤ nums.length ≤ 12
◆-1000 ≤ nums[i] ≤ 1000
◆If more than one longest increasing subsequence exists, return the one that ends at the earliest-finishing chain — built by always preferring the smallest-index predecessor whenever two predecessors would extend a chain to the same length

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Recursive Backtrack After Building the DP Table

Optimal

First fill a length-only dp[i] table exactly like the length-only version of this problem: dp[i] holds the length of the longest increasing subsequence ending at index i, found by checking every earlier index j and extending dp[j] whenever nums[j] is smaller. A parent[i] array is filled alongside it, recording which earlier index produced dp[i]'s best value — only updating on a strict improvement, so the first predecessor to reach a given length is the one kept. Once every index is filled, the index holding the largest dp value marks where the answer ends. A small recursive helper then walks parent pointers back to the start, and — because it appends the current index's value only after recursing on its parent — the values land in the result in correct left-to-right order automatically.

TimeO(n²)

SpaceO(n)

Java

Try it out

class Solution {
    public int[] printLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && 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> result = new ArrayList<>();
        backtrack(nums, parent, maxIdx, result);
        int[] out = new int[result.size()];
        for (int k = 0; k < out.length; k++) out[k] = result.get(k);
        return out;
    }

    private void backtrack(int[] nums, int[] parent, int i, List<Integer> result) {
        if (i == -1) return;
        backtrack(nums, parent, parent[i], result);
        result.add(nums[i]);
    }
}

Iterative Backtrack After Building the DP Table

Approach

Build the exact same dp[]/parent[] tables as the recursive version. Since dp[maxIdx] already says how long the final answer is, a result array of that exact size can be allocated up front and filled from its last slot backward: starting at maxIdx, place its value in the last slot, step to parent[maxIdx], place that value one slot earlier, and keep following parent pointers until one points to nothing (-1). Filling from the back removes the need for any separate reversal step at the end.