Longest Increasing Subsequence

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Examples

The brute-force approach

Generate all subsequences and find the longest one that is strictly increasing.

best = 0
for mask in range(1 << n):
    subseq = [nums[i] for i in range(n) if mask & (1 << i)]
    if all(subseq[i] < subseq[i+1] for i in range(len(subseq)-1)):
        best = max(best, len(subseq))
return best

O(2^n × n) — trying all subsets.

Spotting the pattern

This is a Dynamic Programming problem. The key question to ask yourself:

If you know the longest increasing subsequence ending at each index before i, how do you compute the longest one ending at index i?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.