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

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = input.nextInt();
        }
        //思路：dp数组存储以对应数字为结尾的最长严格上升子序列长度
        //从第二个数开始向前遍历，找到比它小的数中最大的dp值，然后+1
        int[] dp = new int[n];
        dp[0] = 1;
        int index;
        int max;
        for (int i = 1; i < n; i++) {
            index = i - 1;
            max = 0;
            while (index >= 0) {
                if (arr[index] < arr[i] && dp[index] > max) {
                    max = dp[index];
                }
                index --;
            }
            dp[i] = max + 1;
        }
        int res = dp[1];
        for (int i = 1; i < n; i++) {
            res = Math.max(res, dp[i]);
        }
        System.out.println(res);
    }
}