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

定义dp[i] : 以i结尾的最长上升子序列长度

状态转移 : dp[i] = Math.max(dp[i],dp[j](j->(0,i-1)+1); 并且是arr[i] > arr[j] 的情况下才能转移

初始化dp[i] 都为1 因为他们自己本身就是一个最长上升子序列

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if(n==0){
            System.out.println(0);
            return;
        }
        int[] arr = new int[n];
        for(int i = 0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        //dp[i] : 以i结尾的最长上升子序列长度
        int ans = 1;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for(int i = 1;i<n;i++){
            for(int j = 0;j<i;j++){
                if(arr[i]>arr[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            ans = Math.max(ans,dp[i]);
        }
        System.out.println(ans);
    }
}