网站建设人工费,买空间送网站,去别人网站挂黑链,仙居谁认识做网站的LIS算是比较经典的问题#xff0c;常用的是O(n^2)的方法 for(int i1;in;i){dp[i]1;for(int j1;ji;j){if(a[j]a[i])dp[i]max(dp[i],dp[j]1);}mxmax(mx,dp[i]);}我们这里优化成O(nlogn) 我们模拟一个栈stack#xff0c;每读入一个数#xff0c;如果这个数大于栈顶…LIS算是比较经典的问题常用的是O(n^2)的方法 for(int i1;in;i){dp[i]1;for(int j1;ji;j){if(a[j]a[i])dp[i]max(dp[i],dp[j]1);}mxmax(mx,dp[i]);}
我们这里优化成O(nlogn) 我们模拟一个栈stack每读入一个数如果这个数大于栈顶的数就将它压入栈内 这样栈内元素都是递增的如果读入元素小于栈顶元素因为栈内是递增的所以我们就二分查找栈内第一个大于它的数并替换它。最长序列长度即为最后模拟的大小 对于i和j如果i j且a[i] a[j],用a[i]替换a[j]长度虽然没有改变但a的’潜力’增大了。
代码
#include iostream
using namespace std;
int i,j,n,s,t,a[100001];
int main()
{cinn;a[0]-1000000;for(i0;in;i){cint;if(ta[s]) a[s]t;else{int l1,hs,m;while(lh){m(lh)/2;if(ta[m]) lm1;else hm-1;}a[l]t;}}coutsendl;
}
