CF-580A

題目大意

求最長的連續(xù)不下降子序列。

題目分析

設(shè)f[x]表示以x這個(gè)位置結(jié)尾的最長不下降子序列的長度，那么f[x-1]與f[x]的關(guān)系很顯然取決于a[x]與a[x-1]的關(guān)系.如果a[x]>=a[x-1]，顯然要f[x] = f[x-1] + 1;否則f[x] = 1，從頭再來。

掃描一遍，以1~n結(jié)尾的最長連續(xù)不下降子序列，得到最大的那個(gè)就可以了。

參考代碼

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