Python longest increasing subsequence: reconstruct a strict sequence from tail candidates

Operation contract

The algorithm maintains the smallest known ending value for each subsequence length. bisect_left finds where a value replaces a tail or extends the candidate lengths. Each chosen input position retains a predecessor pointing to the prior length candidate at that time. Walking those links from the final tail reconstructs a valid subsequence; the tail array itself is not the reconstructed input sequence. Equal values replace a candidate rather than extend a strict subsequence.

Failure and ownership boundary

The fixture accepts at most 128 exact integers in a bounded range, rejects Booleans and returns one optimum, without promising the lexicographically first optimum. A nondecreasing policy would change the binary-search boundary. Python bisect: binary position search does not make list insertion logarithmic, Python longest common subsequence: rolling-row DP and its limits and Python edit scripts: reconstruct and verify an alignment instead of only counting it address related choices.

Working program

from bisect import bisect_left

def increasing_subsequence(amounts):
    if type(amounts) is not list or len(amounts) > 128 or any(type(amount) is not int or not -1000000 <= amount <= 1000000 for amount in amounts):
        raise ValueError("bounded exact integers required")
    tails, positions, previous = [], [], [-1] * len(amounts)
    for index, amount in enumerate(amounts):
        length_index = bisect_left(tails, amount)
        if length_index:
            previous[index] = positions[length_index - 1]
        if length_index == len(tails):
            tails.append(amount)
            positions.append(index)
        else:
            tails[length_index] = amount
            positions[length_index] = index
    result = []
    cursor = positions[-1] if positions else -1
    while cursor != -1:
        result.append(amounts[cursor])
        cursor = previous[cursor]
    return list(reversed(result))

print("selected:", increasing_subsequence([300, 100, 200, 200, 400, 250]))
print("duplicates:", increasing_subsequence([125, 125, 125]))
print("empty:", increasing_subsequence([]))

Output

selected: [100, 200, 250]
duplicates: [125]
empty: []

Costs and limits

Binary search for each of n values gives O(n log n) time, while predecessor and candidate arrays need O(n) storage. Reconstructing the returned sequence is O(L) for optimum length L. Input magnitude is bounded here, so comparisons do not hide unbounded integer digit work.

Common Mistakes

• Tail values need not form the returned subsequence by themselves.
• Strict increase cannot extend a sequence using an equal value.

Connected lessons

Python bisect: binary position search does not make list insertion logarithmic, Python longest common subsequence: rolling-row DP and its limits, Python edit scripts: reconstruct and verify an alignment instead of only counting it.