题解 | #Redraiment的走法#

拿例子的序列来说， 2 5 1 5 4 5。我会逐步解释每一步的计算过程。

首先，我们初始化 dp 数组为 [1, 1, 1, 1, 1, 1]，因为每个元素自身就构成了一个长度为1的递增子序列。

然后，我们开始逐个考虑每一个元素。

1. 对于元素 2，它之前没有其他元素，所以 dp[1] 保持为1。
2. 对于元素 5，它之前只有一个元素 2，而且 2 小于 5，所以我们可以将 5 接在 2 后面形成一个递增子序列。因此，dp[2] = Math.max(dp[2], dp[1] + 1) = Math.max(1, 2) = 2。
3. 对于元素 1，它之前的元素 2 和 5 都比它大，所以 dp[3] 保持为1。
4. 对于元素 5，它之前的元素有 2 和 1 是小于它的，所以我们可以将 5 接在 2 或 1 后面形成一个递增子序列。我们选择长度更长的那个，所以 dp[4] = Math.max(dp[4], dp[1] + 1, dp[3] + 1) = Math.max(1, 2, 2) = 2。
5. 对于元素 4，它之前的元素有 2 和 1 是小于它的，所以我们可以将 4 接在 2 或 1 后面形成一个递增子序列。我们选择长度更长的那个，所以 dp[5] = Math.max(dp[5], dp[1] + 1, dp[3] + 1) = Math.max(1, 2, 2) = 2。
6. 对于元素 5，它之前的元素有 2、1 和 4 是小于它的，所以我们可以将 5 接在 2、1 或 4 后面形成一个递增子序列。我们选择长度更长的那个，所以 dp[6] = Math.max(dp[6], dp[1] + 1, dp[3] + 1, dp[5] + 1) = Math.max(1, 2, 2, 3) = 3。

最后，dp 数组变为了 [1, 2, 1, 2, 2, 3]。最长的递增子序列的长度就是 dp 数组中的最大值，也就是 3。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 创建一个新的Scanner对象，用于读取从控制台输入的数据
        Scanner in = new Scanner(System.in);

        // 使用一个while循环，处理多个测试用例。当有下一个输入时，循环继续执行
        while (in.hasNext()) {

            // 读取控制台输入的第一行数据，即梅花桩的个数，并转换为整数类型
            int n = Integer.parseInt(in.nextLine());

            // 读取控制台输入的第二行数据，即每个梅花桩的高度，并去除首尾的空格
            String s = in.nextLine().trim();

            // 使用空格将读入的字符串进行分割，得到一个包含所有梅花桩高度的字符串数组
            String str[] = s.split(" ");

            // 定义一个长度为n+1的动态规划数组dp，用于存储每个位置的最长递增子序列的长度
            int dp[] = new int[n + 1];

            // 初始化dp数组。对于每一个梅花桩，它本身就是一个长度为1的递增子序列
            for (int j = 1; j <= n; j++) {
                dp[j] = 1;
            }

            // 定义一个变量maxLen，用于存储最长递增子序列的长度。初始值为1，因为至少有一个梅花桩
            int maxLen = 1;

            // 对于每一个梅花桩j
            for (int j = 1; j <= n; j++) {

                // 对于梅花桩j之前的每一个梅花桩i
                for (int i = 1; i < j; i++) {

                    // 如果梅花桩i的高度小于梅花桩j的高度，则可以从梅花桩i跳到梅花桩j
                    if (Integer.parseInt(str[i - 1]) < Integer.parseInt(str[j - 1])) {

                        // 更新dp[j]，取dp[i]+1（即在原有的基础上跳到梅花桩j）和dp[j]（即不从梅花桩i跳到梅花桩j）中的较大值
                        dp[j] = Math.max(dp[j], dp[i] + 1);
                    }
                }

                // 更新最长递增子序列的长度，取maxLen和dp[j]中的较大值
                maxLen = Math.max(maxLen, dp[j]);
            }

            // 输出最长递增子序列的长度
            System.out.println(maxLen);
        }
    }
}