7-11 LIS (10 分)
The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}
Input specifcation:
There is a number n in the first line,that means how many numbers in the mainsequence.There are n numbers in the second line.
Output specifcation:
output a number m in the first line,that means the length of the longest increasing subsequence.Then output the m numbers of the longest increasing subsequence in the second line.
input example:
9
10 22 9 33 21 50 41 60 80
###output example:
6
10 22 33 50 60 80
作者
严华云
单位
湖州师范学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include<bits/stdc++.h>
using namespace std;
int a[1000],b[1000],c[1000],n;
void lis(int x){
if(x==0) return;
lis(c[x]);
cout<<a[x]<<" ";
}
int main(){
cin>>n;
int i,j,k,len,maxlen=0,index;
for(i=1;i<=n;i++)
cin>>a[i];
b[1]=1;
for(i=2;i<=n;i++){
len=0;
for(j=1;j<i;j++){
if(a[j]<a[i]&&b[j]>len){
len=b[j];
index=j;
}
}
b[i]=len+1;
c[i]=index;
}
for(i=1;i<=n;i++){
if(maxlen<b[i]){
maxlen=b[i];
index=i;
}
}
cout<<maxlen<<endl;
lis(index);
return 0;
}