这道题是最长上升子序列的变形题 AC代码 最长上升子序列的枚举对象是每一个a[i]为终点的上升子序列,之后在a[i]前面的序列里找到最长的上升子序列。 递推式: Maxlen[1]=1; Maxlen[k]=Max{Maxlen(for i (1<i<k) ) }+1 Maxlen[k]指的就是以k为下表的数组元素为终点的最大上升子序列的长度。
#include<bits/stdc++.h>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
const int N =1e5+5;
int n;
struct cmp {
bool operator()(const int&a,const int&b) const {
return a>b;
}
};
//int month[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31};
int a[30];
int b[30];
int main() {
cin >>n;
for(int i =1;i<=n;i++){
cin >>a[i];
}
b[1]=1;
for(int i =2;i<=n;i++){
int temp = 0;
for(int j =1;j<i;j++){
if(a[i]<=a[j])
{
if(temp<b[j])
temp = b[j];
}
}
b[i]=temp+1;
//cout<<b[i]<<" ";
}
int ans =-1;
for(int i =1;i<=n;i++){
if(ans <b[i])
{
ans = b[i];
}
}
cout<<ans<<endl;
return 0;
}
//3
//203 200 300