HJ103 Redraiment的走法 | 题解

• 状态定义：

  • dp[i] 的值代表 nums 以 nums[i] 结尾的最长子序列长度。

• 转移方程： 设 j∈[0,i)j∈[0,i)，考虑每轮计算新 dp[i] 时，遍历 [0,i) 列表区间，做以下判断：

  1. 当 nums[i]>nums[j] 时： nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j]+1 ；
  2. 当 nums[i]<=nums[j] 时： nums[i] 无法接在nums[j] 之后，此情况上升子序列不成立，跳过。
  • 上述所有 1. 情况 下计算出的 dp[j]+1 的最大值，为直到 ii 的最长上升子序列长度（即 dp[i] ）。实现方式为遍历 j 时，每轮执行 dp[i]=max(dp[i],dp[j]+1)。
  • 转移方程： dp[i] = max(dp[i], dp[j] + 1) 。

• 初始状态：

  • dp[i] 所有元素置 1，含义是每个元素都至少可以单独成为子序列，此时长度都为 1。

• 返回值：

  • 返回 dp 列表最大值，即可得到全局最长上升子序列长度。

复杂度分析：

• 时间复杂度 O(N^2) ： 遍历计算 dp 列表需 O(N)，计算每个 dp[i] 需 O(N)。
• 空间复杂度 O(N) ： dp 列表占用线性大小额外空间。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = in.nextInt();
            }
            if (n <= 1)
                System.out.println(n);
            int[] dp = new int[n];
            Arrays.fill(dp,1);
            int res = 0;
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j])
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                if (dp[i] > res)
                    res = dp[i];
            }
            System.out.println(res);
        }
    }
}