O(nlogn)的最长上升子序列并且记录所选择的数模板

#include <iostream>#include <cstdlib>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>using namespace std;const int MAXN = 10000 + 10;int A[MAXN];int lis[MAXN];int f[MAXN];int stack[MAXN];int N;int main(){while(scanf("%d", &N)!=EOF){for(int i=1;i<=N;i++)scanf("%d", &A[i]);int top = 1;stack[1] = A[1];f[1] = 1;for(int i=2;i<=N;i++){if(A[i] > stack[top]){stack[++top] = A[i];f[i] = top;}else{int pos = lower_bound(stack, stack + top, A[i]) – stack;stack[pos] = A[i];f[i] = pos;}}cout << top << endl;int t = top;for(int i=N;i>=1;i–){if(f[i] == t){lis[–t] = i;}if(t < 0) break;}for(int i=0;i<top;i++)cout << lis[i] << ' ';cout << endl;}return 0;}

，我没有值得分享的感伤爱情故事，

相关文章：

你感兴趣的文章：

标签云：