动态规划解法

就按题目中的示例来讲吧，首先我们肯定把复杂问题向简单问题靠拢，只有找到简单和复杂之间的转换规律

 2 5 1 5 4 5 

一开始我的思路是想，第一步踩 2 这个数，第二步又分情况，可以踩三个5中的任意一个，或踩4 ，第三步再踩5（前提是第二步踩得是4）。但是这个解法似乎只能暴力破解，枚举所有的情况。

思路：

如果我最后一步踩的是：最后一位的5，那么我前一步只能踩2、4。如果我前一步是4，那么前一步的前一步就只能踩2。看出来了吗？

踩5的时候，假设走得步数为n，那么4就是n-1，2就是n-2。它的步数是前一个可踩的数的步数加1。假设F[i]表示第i个数走的步数，那么：

F[i] = F[j] + 1
F[j]表示第j个数走的步数，j按题意要求必须是在i之前，也就是j 可能是 0 -i 之间所有可能的数。
且j位置上的数必须小于i位置上的数。

由于j可能的值很多，我们要求的是最多步数，也就是最大的F[j]。所以遍历的时候把最大的值保留下来即可

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            int n = Integer.parseInt(in.nextLine());
            String[] s = in.nextLine().split(" ");
            int[] nums = new int[n];
            for (int i = 0; i < nums.length; i++) {
                nums[i] = Integer.parseInt(s[i]);
            }
            //上面是处理输入：n 是有多少根柱子，nums是每个主子的高度
            int max = 1;
            //下面是关键代码
            int[] step = new int[n];
            for (int j = 0; j < n; j++) {
                step[j] = 1;
                for (int k = 0; k < j; k++) {
                    if (nums[k] < nums[j]) {
                        step[j] = Math.max(step[k] + 1, step[j]);
                    }
                }
                max = Math.max(max, step[j]);
            }
            System.out.println(max);
        }
    }
}