求最长上升子序列(二分+动态规划)
因为数组比较大,所以在n^2的话可能卡是时间,所以有了另外一种方法(动态规划+二分)可以说是全新的方向,代码很简单,但是主要的思路还是很巧妙的,一开始有点难理解。
aa[]就是原数组,遍历一遍。
f[]这个我好像讲不明白,试一下,
假设f[3]=7, 3 是上升序列长度,7 是最后一位数(不断更新找到最小的值),后面可能变成f[3]=5,或者更小的f[3]=4。
1,2,7,4,3......类似这样的。所以最后结束的时候,后面的f[4]=p0必定要比f[3]=p1的值更大才行.
所以这个二分法找的是比aa[i]小的最大的数。
比如:7,3,5,9,如果aa[i]=6,那么找到的数是5,(假想为:f[3]=9,变成了f[3]=6),数组假设为7,3,5,9,6.
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int aa[100010];
int f[100010];
int main() {
cin >> n;
for (int i = 0; i < n; i++)cin >> aa[i];
int len = 0;
f[0] = -2e9;
for (int i = 0; i < n; i++) {
int l = 0,r = len;
while (l < r) {
int mid = l + r + 1 >> 1;//二分
if (f[mid] < aa[i])l = mid;
else r = mid - 1;
}
len = max(len, r + 1);
f[r + 1] = aa[i];
}
cout << len << endl;
}