Longest Increasing Subsequence (LIS)

The longest increasing subsequence problem asks for the maximum length of a strictly increasing subsequence in an array. This lesson covers the classic O(n²) DP (LeetCode 300), the optimized O(n log n) patience-sorting approach, and full solutions in C, Java, and Python with output trace tables.

Overview

Given an integer array nums, find the length of the longest strictly increasing subsequence. A subsequence keeps relative order but may skip elements.

• Subsequence — not necessarily contiguous (e.g. [2, 3, 7, 101] from the array below)
• Strictly increasing — each next element must be greater than the previous
• Two standard solutions — O(n²) DP for clarity; O(n log n) with binary search for interviews

Example: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Index:         0   1  2  3  4  5   6    7

One LIS of length 4:  2 → 3 → 7 → 101   (indices 2, 4, 5, 6)
Another:              2 → 5 → 7 → 101   (indices 2, 3, 5, 6)
Answer (length only): 4

LIS — O(n²) Dynamic Programming

State: dp[i] = length of the longest increasing subsequence that ends at index i.

Recurrence: For each j < i where nums[j] < nums[i], update dp[i] = max(dp[i], dp[j] + 1).

Base: Every single element is a subsequence of length 1 → initialize dp[i] = 1.

Answer: max(dp) over all indices.

O(n²) LIS Code (C, Java, Python)

Python

def length_of_lis(nums):
    """LeetCode 300 — O(n²) DP. dp[i] = LIS length ending at index i."""
    n = len(nums)
    if n == 0:
        return 0

    dp = [1] * n  # each element alone is length 1
    best = 1

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
        best = max(best, dp[i])

    return best


if __name__ == "__main__":
    tests = [
        [10, 9, 2, 5, 3, 7, 101, 18],
        [0, 1, 0, 3, 2, 3],
        [7, 7, 7, 7],
    ]
    for nums in tests:
        print(f"nums={nums} → LIS length = {length_of_lis(nums)}")

Java

public class LisOn2 {

    /** O(n²) LIS — bottom-up DP ending at each index. */
    public static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;

        int[] dp = new int[n];
        int best = 1;

        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            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) {
        System.out.println(lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18})); // 4
        System.out.println(lengthOfLIS(new int[]{0, 1, 0, 3, 2, 3}));             // 4
        System.out.println(lengthOfLIS(new int[]{7, 7, 7, 7}));                   // 1
    }
}

C

#include <stdio.h>

#define MAX_N 10000

/* O(n²) LIS length */
int lis_on2(int nums[], int n) {
    int dp[MAX_N];
    int i, j, best = 1;

    if (n == 0) return 0;

    for (i = 0; i < n; i++) {
        dp[i] = 1;
        for (j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > best) best = dp[i];
    }
    return best;
}

int main(void) {
    int a[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int b[] = {0, 1, 0, 3, 2, 3};
    int c[] = {7, 7, 7, 7};
    printf("%d\n", lis_on2(a, 8)); /* 4 */
    printf("%d\n", lis_on2(b, 6)); /* 4 */
    printf("%d\n", lis_on2(c, 4)); /* 1 */
    return 0;
}

O(n²) Output & Trace

Program output (all three languages)

DP trace — nums = [10, 9, 2, 5, 3, 7, 101, 18]

LIS — O(n log n) Patience Sorting

The optimized approach maintains an array tails where tails[k] is the smallest possible tail value of an increasing subsequence of length k + 1.

For each num in nums:

1. Binary search tails for the leftmost index where tails[i] ≥ num
2. If found, replace tails[i] = num (improve the tail for that length)
3. If not found, append num (extend LIS by one)

Final answer = len(tails). Time O(n log n), space O(n).

O(n log n) LIS Code (C, Java, Python)

Python

def length_of_lis_nlogn(nums):
    """LeetCode 300 — O(n log n) via patience sorting + binary search."""
    tails = []

    for num in nums:
        left, right = 0, len(tails)
        # find first index with tails[i] >= num
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid

        if left == len(tails):
            tails.append(num)       # extend LIS length
        else:
            tails[left] = num       # replace smaller tail

    return len(tails)


if __name__ == "__main__":
    tests = [
        [10, 9, 2, 5, 3, 7, 101, 18],
        [0, 1, 0, 3, 2, 3],
        [7, 7, 7, 7],
    ]
    for nums in tests:
        print(f"nums={nums} → LIS length = {length_of_lis_nlogn(nums)}")

Java

public class LisNLogN {

    /** O(n log n) LIS using tails array and binary search. */
    public static int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;

        for (int num : nums) {
            int left = 0, right = size;
            while (left < right) {
                int mid = (left + right) / 2;
                if (tails[mid] < num) left = mid + 1;
                else right = mid;
            }
            if (left == size) {
                tails[size++] = num;
            } else {
                tails[left] = num;
            }
        }
        return size;
    }

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

C

#include <stdio.h>

#define MAX_N 10000

/* Binary search: first index in tails[0..size-1] where tails[i] >= num */
int lower_bound(int tails[], int size, int num) {
    int left = 0, right = size;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (tails[mid] < num) left = mid + 1;
        else right = mid;
    }
    return left;
}

int lis_nlogn(int nums[], int n) {
    int tails[MAX_N];
    int size = 0, i, pos;

    for (i = 0; i < n; i++) {
        pos = lower_bound(tails, size, nums[i]);
        if (pos == size) tails[size++] = nums[i];
        else tails[pos] = nums[i];
    }
    return size;
}

int main(void) {
    int a[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int b[] = {0, 1, 0, 3, 2, 3};
    int c[] = {7, 7, 7, 7};
    printf("%d\n", lis_nlogn(a, 8)); /* 4 */
    printf("%d\n", lis_nlogn(b, 6)); /* 4 */
    printf("%d\n", lis_nlogn(c, 4)); /* 1 */
    return 0;
}

O(n log n) Output & Trace

Program output

Tails array evolution — nums = [10, 9, 2, 5, 3, 7, 101, 18]

LIS Variants & Related Problems

Connect to subsequence problems for LCS and related string DP, and to knapsack when selection under constraints appears.

More Examples

Example 1: All decreasing

Example 2: Already sorted

Example 3: Complexity summary

Approach Comparison

Real-Life Applications

LIS models finding the longest monotonically improving pattern in ordered data — trends, rankings, and timelines where each next pick must beat the previous.

Interview Tips

1. Clarify: strictly increasing or non-decreasing? Return length or actual subsequence?
2. Start with O(n²): define dp[i] as LIS ending at i, base case 1.
3. Trace a small array (4–5 elements) on the whiteboard before coding.
4. Offer O(n log n) with tails + binary search as the optimized solution.
5. Explain that tails is not the LIS itself — only length unless you add parent tracking.
6. For envelopes (354): sort by width ascending, height descending, then LIS on heights.
7. State complexities: O(n²) time O(n) space vs O(n log n) time O(n) space.
8. Connect to LCS / subsequence DP when strings replace arrays.