一、数字三角形

二、最长上升子序列

1、基本思想、模板

• 如果序列的元素越紧凑（相邻元素差值尽可能小），同时序列末尾的元素越小就也有可能使得序列增长
• 严格单调：对于相等元素替换，末尾必须严格大于
• 非严格单调：对于相等元素不替换，末尾元素可相等

# 求序列a中的严格单调最长上升子序列
def find(x):
    l, r = 0, len(q) - 1
    while l < r:
        mid = (l + r) >> 1
        if q[mid] >= x:
            r = mid
        else:
            l = mid + 1
    return l

q = [a[0]]
for i in range(n):
    if a[i] > q[len(q) - 1]:
        q.append(a[i])
    else:
        pos = find(a[i])
        q[pos] = a[i]
print(len(q))

2、 怪盗基德的滑翔翼

• 基德可以从中间任意移动房屋向左或右向下滑翔
• 等价于正向和逆向的最长上升子序列

3、 登山

• 队员们先上山再下山，可以正向做一次上升序列然后再逆向做一次，枚举中间点即可
• 相比于（怪盗基德的滑翔翼）来说，只需要记录每一段的结果即可

4、 合唱队形

• 合唱队形是先上升后下降，类似于登山
• 去掉的即为同学即 $总人数 - 最长合唱队形$

5、 友好城市

• 在众多横向排列的对偶中，选取尽可能多满足两两对偶间不相交的对偶
• 固定一个方向为升序（降序），则另一边做上升（下降）子序列即可

6、 最大上升子序列和

• 类似于最长上升子序列，仅是在保持上升的同时取和即可

import sys
input = lambda: sys.stdin.readline().strip()

n = int(input())
a = list(map(int, input().split()))
f = [0] * (n + 1)

for i in range(n):
    f[i] = a[i]
    for j in range(i):
        if a[j] < a[i]:
            f[i] = max(f[i], f[j] + a[i])

print(max(f))

7、拦截导弹

• 拦截最多的导数数目 = 最长非严格下降子序列
• 拦截系统的最少数目 = 最长严格上升子序列

三、最长公共子序列

1、 最长公共子序列

2、 最长公共上升子序列