最长（不）上升子序列

直接用lower_bound()和upper_bound()进行二分查找

 1     b[0] = a[0];
 2     //最长不上升子序列
 3     for (int i = 1; i < cnt; i++) {
 4         if (b[cnt1] >= a[i])
 5             b[++cnt1] = a[i];//序列向后移
 6         else {
 7             int x = upper_bound(b, b + cnt1, a[i], greater<int>()) - b;//降序查找
 8             b[x] = a[i];//找到第一个小于a[i]，将它替换
 9         }
10 
11     }
12     memset(b, 0, sizeof(b));
13     b[0] = a[0];
14     //最长上升子序列
15     for (int i = 1; i < cnt; i++) {
16         if (a[i] > b[cnt2])
17             b[++cnt2] = a[i];//序列向后移
18         else {
19             int x = lower_bound(b, b + cnt2, a[i]) - b;//升序查找
20             b[x] = a[i];//找到第一个大于等于a[i],替换
21         }
22     }