题解 | #拦截导弹#

#include <stdio.h>

int main() {
    int n;
    int h[2000];
    int data[2][2000];
    int i, j, res;
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%d", &(h[i]));
    }

    for(i=n-1, data[0][n] = 1; i>0; i--)
    {
        data[0][i] = 1;
        for(j=i+1; j<=n; j++)
        {
            if(h[i]>=h[j] && data[0][j]+1>data[0][i])
            {
                data[0][i] = data[0][j] + 1;
            }
        }   
    }

    for(i=2, data[1][1] = 1; i<=n; i++)
    {
        data[1][i] = 1;
        for(j=i-1; j>0; j--)
        {
            if(h[i]>h[j] && data[1][j]+1 > data[1][i])
            {
                data[1][i] = data[1][j] + 1;
            }
        }   
    }

    for(res = data[0][1], i=2; i<=n; i++)
    {
        if(data[0][i] > res)
            res = data[0][i];
    }
    printf("%d\n", res);
    for(res = data[1][1], i=2; i<=n; i++)
    {
        if(data[1][i] > res)
            res = data[1][i];
    }
    printf("%d\n", res);
    return 0;
}