题解 | #最长上升子序列(一)#

import java.util.Objects; import java.util.Scanner;

/**

• 动态规划算法练习专题
• 1、AB37 最长上升子序列
• 2、
• 3、
• 4、 */ public class DynamicAlgorithmTest { public static void main(String[] args) { // 构造输入 Scanner sc = new Scanner(System.in); // 1、第一行输入一个正整数 n 表示数组的长度 int n = sc.nextInt(); // 2、第二行输入 n 个整数表示数组的每个元素 int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } upSort(n, a);

/* // 3、查看构造的输入数组 System.out.print("["); for (int i = 0; i < a.length; i++) { if (i == a.length - 1) { System.out.println(a[i] + "]"); break; } System.out.print(a[i] + ","); } */

}

public static void upSort(int len, int[] arr) {
    // f[i] 表示以下标为i的数字结尾的最长上升子序列的长度
    // 用一个数组来存储当前最长子序列的长度
    int[] f = new int[len];
    for (int i = 0; i < len; i++) {
        f[i] = 1;
        for (int j = 0; j < i; j++) {
            // 若后面的数比前面的数更大，则更新最长子序列的长度+1
            if (arr[j] < arr[i]) {
                f[i] = Math.max(f[i], f[j] + 1);
            }
        }
    }
    // 输出最长子序列的长度
    int ans = 1;
    for (int i = 0; i < len; i++) {
        ans = Math.max(ans, f[i]);
    }
    System.out.println(ans);
}

}