XYNUOJ 最长上升子序列

 最长上升子序列

时间限制: 1 Sec   内存限制: 128 MB 提交: 19   解决: 10 [ 提交][ 状态][ 讨论版]

题目描述

给出一个由n个数组成的序列A[1..n]，求最长单调上升子序列（LIS)的长度。LIS即求最大的一个子序列长度m，使得a1<a2<……<am且A[a1]<A[a2]<……<A[am]。

输入

两行：

第1行：整数n (1<=n<=1000)

第2行：n个整数 （int范围内），空格隔开。

输出

一行：一个整数，即最长上升子序列长度。

样例输入

10 63 11 21 36 28 20 57 37 82 4

样例输出

5

提示

#include<stdio.h> #include<string.h> int main(){ int n; int a[1005],dp[1005]; while(scanf("%d",&n)!=EOF){ memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++){ scanf("%d",&a[i]); } for(int i=0;i<n;i++){ dp[i]=1; for(int j=0;j<i;j++){ if(a[j]<a[i]&&dp[j]+1>dp[i]){ dp[i]+=1; } } } int ans=0; for(int i=0;i<n;i++){ if(dp[i]>ans){ ans=dp[i]; } } printf("%d\n",ans); } return 0; }