CF-580A
题目大意
求最长的连续不下降子序列。
题目分析
设f[x]表示以x这个位置结尾的最长不下降子序列的长度，那么f[x-1]与f[x]的关系很显然取决于a[x]与a[x-1]的关系.如果a[x]>=a[x-1]，显然要f[x] = f[x-1] + 1;否则f[x] = 1，从头再来。
扫描一遍，以1~n结尾的最长连续不下降子序列，得到最大的那个就可以了。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn], d[maxn];
int main(){
int n;
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d", &a[i]);
d[1] = 1;
int maxx = 1;
for(int i=2; i<=n; i++){
if(a[i]>=a[i-1])
d[i] = d[i-1]+1;
else
d[i] = 1;
maxx = max(maxx, d[i]);
}
printf("%d", maxx);
return 0;
}
网友评论