Redraiment的梅花桩走法

也就是求最长上升子序列（Leetcode 300）

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int num = in.nextInt();
            int[] origin = new int[num];
            int[] dp = new int[num];
            int res = 0;
            //初始化输入的序列和dp数组
            Arrays.fill(dp,1);
            for(int x = 0; x < num; x++){
                origin[x] = in.nextInt();
            }
            //dp[i]表示：到i为止最长的序列长度
            for(int i = 1; i < dp.length; i++){
                for(int j = 0; j <= i; j++){
                    if(origin[j] < origin[i]){
                        dp[i] = Math.max(dp[i],dp[j] + 1);
                    }
                }
                res = Math.max(res, dp[i]);
            }
            System.out.println(res);
        }
    }
}