O(logN)做法:
dp1[i]:=长度为i的非升子序列中末尾元素的最大值
dp2[i]:=长度为i的上升子序列中末尾元素的最小值
注意
dp1中元素可以相等,用upper_bound搜索替换位置.
dp2中元素不可以相等,用lower_bound搜索替换位置.
可参考<<挑战程序设计竞赛>>P65
code:
#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;
int t[100005];
int dp1[100005];
int dp2[100005];
int ans1, ans2;
int main() {
// clock_t start,end;
// start=clock();
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n = 0;
while (cin >> t[++n]);
n--;
/* O(n^2)
for (int j = 1; j <= i; ++j) {
for (int k = 0; k < j; ++k) {
if (t[k] >= t[j] || k == 0) dp1[j] = max(dp1[j], dp1[k] + 1);
if (t[k] < t[j]) dp2[j] = max(dp2[k] + 1, dp2[j]);
ans1 = max(dp1[j], ans1);
ans2 = max(dp2[j], ans2);
}
}
cout << ans1 << endl;
cout << ans2 << endl;
*/
//O(logN)
for(int i=1;i<=n;++i){
dp2[i]=maxn;
}
for(int i=1;i<=n;++i){
*upper_bound(dp1+1,dp1+n+1,t[i],greater<int>())=t[i];
*lower_bound(dp2+1,dp2+n+1,t[i])=t[i];
}
ans1=lower_bound(dp1+1,dp1+n+1,0,greater<int>() )-(dp1+1);
ans2=lower_bound(dp2+1,dp2+n+1,maxn)-(dp2+1);
cout<<ans1<<endl;
cout<<ans2<<endl;
// end=clock();
// cout<<"TIME PASSED:"<<end-start<<endl;
return 0;
}