题解 | #Redraiment的走法#

#include <stdio.h>
#include <string.h>

//一组数
//从任意地点开始 只能从前往后  只能从低到高
// fn   fn-1    n-1 比n < n 那么 ++ n-1比n大 找到一个比n-1大的++
//  n-1 第n-1个 1  n-2个 找到n-1>n-2++ 找不到1
//动态规划,从后往前,当前数能踩到的最大梅花桩数量= max(它之后比它大的数能踩到的最大梅花桩数量)+1


int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {

        int height[n];
        int max[n];
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &height[i]);
        }

        for (int i = n - 1; i >= 0; i--)
        {
            max[i] = 1 ;
            for (int j = i + 1; j < n; j++)
            {
                if (height[j] > height[i])
                {
                    max[i] = (max[j] + 1 > max[i]) ? max[j] + 1 : max[i];
                }
                if (height[j] == height[i])
                {
                    max[i] = (max[j] > max[i]) ? max[j] : max[i];
                }
            }
        }
        int maxstep = 0;
        for (int i = 0; i < n; i++)
        {
            if (maxstep < max[i])
                maxstep = max[i];
        }

        printf("%d\n", maxstep);
    }

    return 0;
}