[基础DP][CF580A]Kefa and First Steps（最长不下降子序列）

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;
}