最长（不）上升子序列
直接用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 }