LIS算是比較經典的問題，常用的是O(n^2)的方法

for(int i=1;i<=n;i++){dp[i]=1;for(int j=1;j<i;j++){if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);}mx=max(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() {cin>>n;a[0]=-1000000;for(i=0;i<n;i++){cin>>t;if(t>a[s]) a[++s]=t;else{int l=1,h=s,m;while(l<=h){m=(l+h)/2;if(t>a[m]) l=m+1;else h=m-1;}a[l]=t;}}cout<<s<<endl; }

總結

以上是生活随笔為你收集整理的LIS最长上升子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。