Longest Increasing Subsequence (Longest Strictly Rising Ordered Subsequence)

• Longest Increasing Subsequence (LIS) – the longest subsequence of strictly increasing values preserving original order.
• State – dp[i] is the length of the longest increasing subsequence ending at index i.
• Recurrence – dp[i] = max(dp[j] + 1) for all j < i where a[j] < a[i], seeded at 1.
• Answer – the maximum over all dp[i], because the LIS can end at any position.
• Quadratic – O(n^2) time scanning all previous indices for each element.
• Optimal – O(n log n) using a tails array with binary search (patience sorting).

What is the Longest Increasing Subsequence?

The Longest Increasing Subsequence (LIS) of an array is the longest subsequence in which the values are strictly increasing while preserving the original order. A subsequence does not require contiguous elements; it only requires that the relative order is maintained.

For example, in the array [10, 9, 2, 5, 3, 7, 101, 18], one LIS is [2, 3, 7, 18] with length 4.

package com.bank.dsa;

public class LisQuadratic {

    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        java.util.Arrays.fill(dp, 1);  // every element alone is a subsequence of length 1
        int best = 1;

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }

    public static void main(String[] args) {
        int[] balances = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("LIS length: " + lengthOfLIS(balances));
    }
}

LIS length: 4

Why does the recurrence look back at every earlier element?

For each index i, we want the longest increasing subsequence that ends exactly at i. Any earlier index j with a smaller value can be the predecessor. So we scan all j < i, and if a[j] < a[i], the subsequence ending at j can be extended by a[i], giving dp[j] + 1. We take the maximum over all such j.

The answer is the maximum dp[i] over all indices, not just dp[n-1], because the LIS can end at any position in the array.

How does the O(n log n) patience sorting approach work?

The optimal approach maintains a tails array where tails[k] holds the smallest possible ending value of an increasing subsequence of length k + 1. For each element, we binary-search for the first tail that is greater than or equal to it. If no such tail exists, the element extends the longest known subsequence and we append it. Otherwise, we overwrite that tail because this element provides a smaller, more extendable ending for that length.

package com.bank.dsa;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LisOptimal {

    public static int lengthOfLIS(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        for (int x : nums) {
            int pos = Collections.binarySearch(tails, x);
            if (pos < 0) pos = -(pos + 1);  // insertion point
            if (pos == tails.size()) {
                tails.add(x);
            } else {
                tails.set(pos, x);
            }
        }
        return tails.size();
    }

    public static void main(String[] args) {
        int[] balances = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("LIS length: " + lengthOfLIS(balances));
    }
}

LIS length: 4

How is the quadratic different from the O(n log n) approach?

| Aspect | Quadratic DP | Patience sorting (O(n log n)) |
|---|---|---|
| Time | O(n^2) | O(n log n) |
| Space | O(n) for dp array | O(n) for tails array |
| Actual subsequence | Reconstruct via predecessor pointers | Tails array is NOT a valid LIS |
| Ease of coding | Simple nested loops | Binary search required |
| Best for | Small arrays or when reconstruction needed | Large arrays where length suffices |

What is the tails array subtlety?

The tails array is not itself a valid increasing subsequence. It stores the smallest possible tail for each achievable length. For example, with input [3, 1, 4, 1, 5], after processing all elements the tails might be [1, 4, 5], but the actual LIS is [1, 4, 5] (which happens to match in this case) or [3, 4, 5]. In general, the tails array only gives the correct length.

To reconstruct the actual subsequence, maintain predecessor pointers alongside the tails.

package com.bank.dsa;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LisReconstruct {

    public static List<Integer> findLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return Collections.emptyList();

        int[] dp = new int[n];
        int[] parent = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(parent, -1);
        int bestIdx = 0;

        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;
                }
            }
            if (dp[i] > dp[bestIdx]) bestIdx = i;
        }

        List<Integer> lis = new ArrayList<>();
        for (int i = bestIdx; i != -1; i = parent[i]) {
            lis.add(nums[i]);
        }
        Collections.reverse(lis);
        return lis;
    }

    public static void main(String[] args) {
        System.out.println(findLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
    }
}

[2, 3, 7, 18]

What are common mistakes?

The most common mistake is returning dp[n-1] instead of the maximum over all dp values. The LIS does not have to end at the last element.

// WRONG: assumes LIS ends at the last element
return dp[n - 1];

// CORRECT: the LIS can end anywhere
int best = 0;
for (int i = 0; i < n; i++) best = Math.max(best, dp[i]);
return best;

Another mistake is using <= instead of < for the comparison, which gives the longest non-decreasing subsequence instead of strictly increasing.

What are the edge cases?

When the array is empty, the answer is zero. When the array has one element, the answer is one. When the array is already sorted in strictly increasing order, the answer is the array length. When the array is strictly decreasing, the answer is one.

package com.bank.dsa;

public class LisEdgeCases {
    public static void main(String[] args) {
        System.out.println(LisQuadratic.lengthOfLIS(new int[]{}));           // 0
        System.out.println(LisQuadratic.lengthOfLIS(new int[]{5}));          // 1
        System.out.println(LisQuadratic.lengthOfLIS(new int[]{1, 2, 3}));    // 3
        System.out.println(LisQuadratic.lengthOfLIS(new int[]{3, 2, 1}));    // 1
    }
}

0
1
3
1

When should you use LIS in banking?

At the National Bank of India, Rajesh analysed a customer's monthly closing balances to find the longest stretch of months where the balance kept strictly rising. A long rising streak was a positive signal in the customer's financial health score for credit decisions.

package com.bank.service;

public class FinancialHealthScorer {

    public static int longestRisingStreak(int[] monthlyBalances) {
        if (monthlyBalances.length == 0) return 0;
        int[] dp = new int[monthlyBalances.length];
        java.util.Arrays.fill(dp, 1);
        int best = 1;
        for (int i = 1; i < monthlyBalances.length; i++) {
            for (int j = 0; j < i; j++) {
                if (monthlyBalances[j] < monthlyBalances[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }

    public static void main(String[] args) {
        int[] balances = {50000, 48000, 52000, 55000, 51000, 60000, 70000};
        System.out.println("Longest rising streak: " + longestRisingStreak(balances) + " months");
    }
}

Longest rising streak: 5 months

What should a senior engineer know?

A senior engineer should know that LIS can also be solved by reducing it to LCS. Sort the array to get a sorted version, then find the longest common subsequence between the original and sorted arrays. The LCS gives the LIS. However, this is O(n^2) and offers no advantage over the direct quadratic DP.

The O(n log n) patience sorting is named after the card game "patience" (solitaire). The number of piles formed when placing cards by the patience sorting rule equals the length of the LIS. This connection is due to the Dilworth theorem.

For the non-strictly increasing variant (longest non-decreasing subsequence), change the binary search from lower_bound to upper_bound.