32. Longest Increasing Confidence Streak

Problem

Fin's model gets re-benchmarked weekly, producing an average confidence score for that week's release. As a signal of sustained improvement (rather than a single lucky week), find the length of the longest streak of strictly increasing scores across the sequence of weekly releases. The streak does not need to be made of consecutive weeks — just weeks in increasing order.

This is the classic Longest Increasing Subsequence problem. It should be solved with the O(n log n) patience-sorting/binary-search version, not the O(n²) DP version.

Source: src/32_most_common_query_pattern.py

def longest_increasing_streak(scores: list[float]) -> int:

>>> longest_increasing_streak([0.1, 0.3, 0.2, 0.4, 0.35, 0.5])
4
>>> longest_increasing_streak([0.5, 0.4, 0.3, 0.2, 0.1])
1

Step-by-Step Approach

1. Maintain a working array tails, where tails[i] is the smallest possible last value of any increasing subsequence of length i + 1 found so far.
2. Walk through the scores one at a time.
3. For each score x, binary-search tails for the leftmost position where x could be inserted to keep it sorted (bisect_left).
4. If that position is past the end of tails, x extends the longest subsequence found so far — append it.
5. Otherwise, x replaces the value at that position, since x is a strictly smaller (or equal) tail for a subsequence of that length, which keeps future extensions more flexible.
6. After processing every score, the length of tails is the answer.

The key insight is that tails is not literally the longest subsequence itself, just a proxy — its length always equals the true LIS length, and keeping each tail as small as possible maximizes future extension opportunities. Using bisect_left instead of bisect_right is what enforces "strictly increasing" instead of "non-decreasing."

Reference solution

from bisect import bisect_left


def longest_increasing_streak(scores: list[float]) -> int:
    # patience sorting: tails[i] = smallest possible tail of an increasing
    # subsequence of length i+1; bisect_left keeps it strict, O(n log n) time, O(n) space
    tails: list[float] = []
    for x in scores:
        # leftmost insert point; enforces strict increase
        idx = bisect_left(tails, x)
        if idx == len(tails):
            # x extends the longest streak so far
            tails.append(x)
        else:
            # x is a smaller tail for that streak length
            tails[idx] = x
    # length of tails == true LIS length, not its contents
    return len(tails)

Key Functions & Tricks

• bisect.bisect_left(a, x) — leftmost sorted-insert index for x in a, O(log n).
• "Tails" array (patience sorting) — tails[i] is the smallest last value of any length-i+1 increasing subsequence found so far.
• Insertion point as streak length — append if x is past the end, else overwrite the first tail >= x.
• bisect_left vs bisect_right — left enforces strictly increasing; right would allow non-decreasing.

How to Recognize This Pattern