最长上升子序列

题目：牛客网

解题思路：（图片来源：https://www.cnblogs.com/frankchenfu/p/7107019.html）

// write your code here
import java.util.Scanner;

public class Main {
	public static int longestupSubsquence(int[] arr){
		int len = arr.length;
		if(len==0)
			return 0;
		int[] num = new int[len];
		num[0]=1;
		for(int i = 1; i < len; i++){
			num[i]=1;
			for(int j = 0; j < i; j++){
				if(arr[j] < arr[i] && num[j]+1 > num[i]){
					num[i]=num[j]+1;
				}
			}
		}
		int max=0;
		for(int i = 0; i < len; i++){
			if(num[i]>num[max]){
				max=i;
			}
		}
		
		return num[max];
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			int len = in.nextInt();
		    int[] arr = new int[len];
		    for(int i = 0; i < len; i++){
		    	arr[i] = in.nextInt();
		    }
			System.out.println(longestupSubsquence(arr));
		}

	}

}