XYNUOJ 最长上升子序列

xiaoxiao2021-02-28  21

 最长上升子序列

时间限制: 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; }
转载请注明原文地址: https://www.6miu.com/read-2450212.html

最新回复(0)