第 12 题

n = len(a)
b = [0] * n
for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            b[i] = max(b[i], b[j] + 1)
print(b[n - 1])

b 的各项初值为 0。外层循环从左到右处理 a[i]，内层循环检查它前面的 a[j]。只有 a[j]<a[i] 时，才允许在以 a[j] 结尾的递增子序列后接上 a[i]，并用 b[j]+1 更新 b[i]；max 保留所有接法中的最大值。由于只含 a[i] 自身时 b[i]=0，而每接入一个更大的元素数值增加 1，所以 b[i] 表示以 a[i] 结尾的最长严格递增子序列长度减 1。子序列须保持原下标顺序，但不要求相邻。最后输出 b[9]，因此只考虑以末尾的 7 结尾的递增子序列。