题解 | 最长不下降子序列

最长不降子序列其实就是把每一个值都考虑一下，如果该值比我列表中最大的都大，那么就直接装进来，如果不是，那么就需要遍历列表去找到第一个大于它的值，然后将这两个值进行替换

注意：这里最后的list其实并不是严格意义上的最长不降子序列，我们也并不关心它是不是，我们只关心它的长度，因为它的长度一定是最长不降子序列的长度

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int a[]=new int[n];
//		往后面遍历，获取到的新值若大于集合最后一个，那么就加上去，若小于最后一个，那么就找到第一个大于它的替换
		for (int i = 0; i < a.length; i++) {
			a[i]=scanner.nextInt();
			
		}
		ArrayList<Integer> list=new ArrayList<>();
		list.add(a[0]);
		for (int i = 1; i < a.length; i++) {
			if(a[i]>list.get(list.size()-1)) {
				list.add(a[i]);
			}else {
				for (int j = 0; j < list.size(); j++) {
					if(list.get(j)>a[i]) {
						list.set(j, a[i]);
						break;
					}
				}
			}
		}
		System.out.println(list.size());

	}

}