Check whether skipping is allowed. A window represents contiguous positions; a subsequence may bridge gaps. For example, [1, 9, 2, 3] has increasing subsequence [1, 2, 3] across a skipped 9.

Let dp[i] be the length of the longest strictly increasing subsequence ending at i. A single element gives length 1. Any earlier j with values[j] < values[i] can be its predecessor.

def lis_length(values):
    dp = [1] * len(values)
    for i in range(len(values)):
        for j in range(i):
            if values[j] < values[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

assert lis_length([1, 9, 2, 3]) == 3
assert lis_length([2, 2, 2]) == 1
assert lis_length([]) == 0

On [1, 9, 2, 3], the table becomes [1, 2, 2, 3]. The final answer is the maximum over endpoints; it need not end at the array’s final position.

There are n states but up to n predecessors each: O(n²) time and O(n) space. Draw an edge j → i when j<i and values[j]<values[i]. This is a DAG because indices increase, and the recurrence finds a longest path length in that implicit graph.

An O(n log n) alternative stores the smallest possible tail value for each subsequence length and uses a binary-search boundary. That requires a new invariant; memorizing it without the state-based baseline hides why replacement is safe. Keep it as a follow-up derivation after this card.

Analogy limit: dp[i] must mean “ending at i,” not simply “best in the first i positions.” Those contracts permit different transitions because only the former guarantees the endpoint’s value.

Use values[j] <= values[i]. The result becomes 3. If using the faster tail-array method, its binary-search boundary must also change to handle equal values correctly.