OR84. 最长递增子序列(LCS)
描述
给定一个序列 An = a1 ,a2 , ... , an ,找出最长的子序列使得对所有 i < j ,ai < aj 。求出这个子序列的长度输入描述
输入的序列输出描述
最长递增子序列的长度示例1
输入:
1 -1 2 -2 3 -3 4
输出:
4
C 解法, 执行用时: 1ms, 内存消耗: 228KB, 提交时间: 2020-04-11
#include<stdio.h> int main(){ int a,b,count=1; scanf("%d",&a); while (scanf("%d",&b)!=EOF){ if(b>a){ count++; a=b; } } printf("%d",count); return 0; }
C 解法, 执行用时: 2ms, 内存消耗: 312KB, 提交时间: 2021-08-24
#include<stdio.h> int main() { int a[1000]={0},i=0,n; int j,t=0,max=0,temp; char c; while (scanf("%d",&a[i++])) { if((c=getchar())=='\n') break; } n=i; for(i=0;i<n;i++) { t=1; temp=a[i]; for(j=i+1;j<n;j++) { if(a[j]>temp) { temp=a[j]; t++; } } if(t>max) max=t; } printf("%d\n",max); return 0; }