题解 | 最长递增子序列（LCS）

1. 动态规划：直接根据当前值和目标比较值的大小关系，更新dp数组即可，注意初始化是"1"不是"0"，因为最短子序列长度是1
2. 贪心算法+二分法搜索：主要要理解tails数组的含义，指定长度的递增子序列的末尾最小值。

# import sys

# for line in sys.stdin:
#     a = list(map(int, line.split()))
#     dp = [1] * len(a)
#     for i in range(len(a)):
#         for j in range(i):
#             if a[i] > a[j]:
#                 dp[i] = max(dp[i], dp[j] + 1)
#     print(max(dp))

import sys

for line in sys.stdin:
    a = list(map(int, line.split()))
    tails = []

    for i in a:
        l, r = 0, len(tails)
        while l < r:
            m = (l+r)//2
            if i < a[m]:
                r = m
            else:
                l = m + 1
        if l == len(tails):
            tails.append(i)
        elif i < tails[l]:
            tails[l] = i
    print(len(tails))