LIS（最大上升子序列）

代码实现如下：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int main() {int arr[500], n, dp[500], ans = -1;scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d", &arr[i]); for(int i = 1; i <= n; i++){dp[i] = 1; //初始化for(int j = 1; j < i; j++){if(arr[j] < arr[i]) // 如果求最大下降子序列则反之dp[i] = max(dp[i], dp[j] + 1);}ans = max(dp[i], ans);}/* ********************************************** */printf("最长子序列的个数为： %d", ans);return 0; }

可进行优化，优化后代码为：

#include<iostream> #include<cstring> #include<string> #include<algorithm> using namespace std; const int maxn=1000+10; int dp[maxn],ans[maxn];int b_search(int x,int s,int len) {while(s<len){int mid=s+(len-s)/2;if(dp[mid]>=x){len=mid;}else{s=mid+1; }}return s; }int main() {int n;while(~scanf("%d",&n)&&n){memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){scanf("%d",&ans[i]);}int len=1;dp[1]=ans[1];for(int i=2;i<=n;i++){if(ans[i]>dp[len]){dp[++len]=ans[i];}else{int p=b_search(ans[i],1,len);dp[p]=ans[i];}}for(int i=1;i<=len;i++){cout<<dp[i]<<" ";}cout<<endl;} }

 

转载于:https://www.cnblogs.com/KasenBob/p/10449878.html

总结

以上是生活随笔为你收集整理的LIS（最大上升子序列）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。