题解 | #Redraiment的走法#

最长递增子序列，使用动态规划进行求解

//最长递增子序列

import java.util.*;

public class Main{
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }
        int[] dp = new int[n]; //使用dp[i]表示以第i个梅花桩结尾的最长步数
        dp[0] = 1;
        for(int i = 1; i < n; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(arr[i] > arr[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int lst = 0;
        for(int i = 0; i < n; i++){
            lst = Math.max(lst, dp[i]);
        }
        System.out.println(lst);
    }
    
}