Crack the Backend

Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence (LIS). A subsequence is obtained by deleting some (or no) elements without changing the order of the remaining elements. "Strictly increasing" means nums[i] < nums[i+1] for consecutive elements in the subsequence.

The subsequence does not need to be contiguous. For example, in [10,9,2,5,3,7,101,18], one LIS is [2,3,7,101] with length 4.
There is an O(n²) DP solution and an O(n log n) solution using binary search + a "tails" array.

Key Observations

Define dp[i] = length of the longest strictly increasing subsequence ending at index i (and including nums[i]). Then dp[i] = 1 + max(dp[j]) over all j < i such that nums[j] < nums[i]. If no such j exists, dp[i] = 1.
The answer is max(dp[0], ..., dp[n-1]). Each dp[i] depends only on earlier indices, so we fill the table in order.
For O(n log n): maintain an array tails where tails[len] is the smallest ending value of an increasing subsequence of length len+1; for each nums[i], binary search to update tails.

Approach

High-level (O(n²)): dp[i] = LIS length ending at i. For each i, look at all j < i with nums[j] < nums[i] and set dp[i] = 1 + max(dp[j]). Return max(dp).

Steps:

dp[i] = 1 for all i initially. For i from 0 to n-1: for j from 0 to i-1, if nums[j] < nums[i], then dp[i] = max(dp[i], 1 + dp[j]).
Return max(dp[0..n-1]).

Implementation

Java

public 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], 1 + dp[j]);
            }
        }

        best = Math.max(best, dp[i]);
    }

    return best;
}

Test Cases

Example 1

Input

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

Expected

4

Explanation

LIS is [2,3,7,101].

Complexity Analysis

Time: O(n^2). O(n log n) with patience sort / binary search.
Space: O(n).

Follow-ups

Reconstruct one LIS; count number of LIS.