Longest Increasing Subsequence (O(n²) DP + O(n log n) patience).

Problem. Given an integer array, return the length of the longest strictly increasing subsequence (elements need not be contiguous). Example: [10,9,2,5,3,7,101,18] → 4 (2,3,7,101).

O(n²) DP

State dp[i] = length of the longest increasing subsequence ending at index i. To extend, look at every earlier j with a smaller value:

dp[i] = 1 + max(dp[j]) for all j < i with nums[j] < nums[i]   (0 if none)

int lengthOfLIS(int[] nums) {
    int n = nums.length, best = 1;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);                  // each element alone is length 1
    for (int i = 1; i < n; 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;
}

Correct and easy to reason about, but the nested loop is O(n²) time, O(n) space.

Optimal — O(n log n) patience sorting

Maintain a tails array where tails[k] is the smallest possible tail of an increasing subsequence of length k+1. For each number, binary-search the first tail >= num and overwrite it (or append if num is largest). The length of tails is the answer. tails is always sorted, so binary search is valid.

int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int x : nums) {
        int lo = 0, hi = size;            // find first tail >= x
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        tails[lo] = x;                    // overwrite or append
        if (lo == size) size++;
    }
    return size;
}

Why it works: replacing a tail with a smaller value never shortens any achievable subsequence and keeps future extensions maximally flexible. The tails array is not itself a valid subsequence — only its length is meaningful.