Longest Increasing Subsequence: the idea to remember.

The core insight

Maintain the smallest possible tail for every subsequence length and replace the first tail at least as large as each value.

Why it works

A smaller tail preserves at least as many future extension opportunities. The tail array length records the longest attainable length.

The mistake to avoid

Use the first tail >= value, not > value, because equal values do not extend a strictly increasing subsequence. Tails is not necessarily an actual subsequence.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int value : nums) {
        int l = 0, r = size;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (tails[m] < value) l = m + 1;
            else r = m;
        }
        tails[l] = value;
        if (l == size) size++;
    }
    return size;
}

Make the next connection