给出长度为N的数组,找出这个数组的最长递增子序列。(递增子序列是指,子序列的元素是递增的)
例如:5 1 6 8 2 4 5 10,最长递增子序列是1 2 4 5 10。
Input
第1行:1个数N,N为序列的长度(2 <= N <= 50000) 第2 - N + 1行:每行1个数,对应序列的元素(-10^9 <= S[i] <= 10^9)
Output
输出最长递增子序列的长度。
Input示例
8 5 1 6 8 2 4 5 10
Output示例
5
刚开始我想到的也是动态规划,然后自己写。提交发现超时了=.=
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int main(){ // freopen("C://Users//Administrator//Desktop//duipai2//1.txt","r",stdin); //freopen("C://Users//Administrator//Desktop//duipai2//out1.txt","w",stdout); int n,i,j,ans=0; int dp[50005]; long long str[50005]; for(i=1;i<50005;i++) dp[i]=1; // memset(dp,1,sizeof(dp)); scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%lld",&str[i]); for(j=1;j<i;j++){ if(str[j]<str[i]&&dp[j]>=dp[i]) dp[i]=dp[j]+1; } } // for(i=1;i<=n;i++) // printf("%d ",dp[i]); for(i=1;i<=n;i++) ans=max(ans,dp[i]); printf("%d ",ans); }
然后参考了网上大神的代码也是动态规划=.=但是优化了,所以AC了~~
#include"stdlib.h" #include"stdio.h" #include"algorithm" using namespace std; const int maxn=1e5; int dp[maxn];//dp[i]表示递增数量i的最小值 int a[maxn]; int main() { int n,len=1; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dp[len]=a[1]; for(int i=2;i<=n;i++) { if(a[i]>dp[len]) dp[++len]=a[i]; else { int pos=lower_bound(dp+1,dp+len,a[i])-dp; //在dp[]找第一个>=a[i]下标 dp[pos]=a[i]; } } // for(int i=1;i<=n;i++) //printf("%d ",dp[i]); //printf(" "); printf("%d ",len); return 0; }