Problem Solving and Structured Thinking Questions

import bisect

def lis_with_reconstruction(a):
    n = len(a)
    tails = []                 # values of tails
    tails_idx = []             # indices in `a` corresponding to tails
    prev = [-1]*n              # predecessor index for reconstruction

    for i, x in enumerate(a):
        # find insertion position (first >= x) to maintain strictly increasing
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
            tails_idx.append(i)
        else:
            tails[pos] = x
            tails_idx[pos] = i

        # set predecessor: element at pos-1's index in original array
        if pos > 0:
            prev[i] = tails_idx[pos-1]

    lis_len = len(tails)

    # Reconstruct one LIS: find index of last element (tails_idx[-1]) and backtrack
    seq = []
    k = tails_idx[-1] if tails_idx else -1
    for _ in range(lis_len):
        seq.append(a[k])
        k = prev[k]
    seq.reverse()
    return lis_len, seq

# Example:
a = [3, 1, 2, 1, 8, 5, 6]
# Tails progression (values) when processing:
# 3 -> [3]
# 1 -> [1]
# 2 -> [1,2]
# 1 -> [1,2]
# 8 -> [1,2,8]
# 5 -> [1,2,5]
# 6 -> [1,2,5,6]
# LIS length = 4, one LIS = [1,2,5,6]