序列问题II | ||||||
| ||||||
Description | ||||||
给一个长度为n的整数序列A0,A1,......An-1,找出最长的非递增子序列的长度 | ||||||
Input | ||||||
输入第一行为数据组数T(T<=20)。 每组数据的第一行为整数的个数n(2<=n<=1000),第二行为n个绝对值不超过150000的整数。 | ||||||
Output | ||||||
对于每组数据,输出最长的非递增子序列的长度。 | ||||||
Sample Input | ||||||
2 3 1 1 3 4 -1 4 3 2 | ||||||
Sample Output | ||||||
2 3 | ||||||
Author | ||||||
陈禹@HRBUST |
题意:不严格的递减序列长度
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
const int N=1e3+3;
int a[N];
int dp[N];
int main(void){
int n,T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) dp[i]=1;
for(int i=2;i<=n;i++){
int dpmax=-1,index=-1;
for(int j=1;j<i;j++){
if(a[j]>=a[i] && dp[j]>dpmax) dpmax=dp[j],index=j;
}
if(index!=-1) dp[i]=dp[index]+1;
}
int mmax=-1;
//for(int i=1;i<=n;i++) printf("%d ",dp[i]);
for(int i=1;i<=n;i++){
mmax=max(mmax,dp[i]);
}
printf("%d\n",mmax);
}
}