动态规划之最长上升子序列模板

今天开始更新动态规划的模板（动态规划哪有模板呀！！！）话是这么说，但我们经常做题会发现有些题目有些共性，我们抽取共性总结出来，应付动态规划基础题目还是可以的。

回归正题，我们今天使用(nlogn)，时间复杂度来写，模板主要使用Java来写（为什么不用c语言呢，因为c语言的模板太多了呀！！！）

我们解释一下原理吧，我们在求最长上升子序列时，可以秉持着尽量使得结尾的数最小的思想，其实也就是贪心，谁让这个贪心比n的平方的普通动规要低时间复杂度呢。我们开个ArrayList不断往里加数字，如果链表为空就直接加入，不为空，如果加入的数字大于链表尾数字，我们加入到链表末端，如果加入的数字小于链表的末尾数字，我们把它找到在链表中第一个大于它的元素的位置，把它替换为我们要加入的元素。在这里我们使用写好的二分方法，大家要注意我们求的是上升子序列不是不下降子序列，一旦我们在ArrayList里边发现一个和我们加入的数字相同的数字，我们必须

放弃加入。

模板题目：

夏令营：动态规划特训 - 【算法模板题】蓝桥勇士 - 蓝桥云课 (lanqiao.cn)

模板：

import java.awt.FontFormatException;
import java.io.BufferedReader; 
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.AnnotatedWildcardType;
import java.math.BigInteger;
import java.sql.SQLIntegrityConstraintViolationException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Spliterator.OfPrimitive;
import java.util.function.IntToDoubleFunction;
import java.util.function.LongBinaryOperator;
import java.util.TreeMap;
import java.util.TreeSet;
import javax.management.relation.InvalidRelationTypeException;
import javax.print.attribute.standard.JobMessageFromOperator;
import javax.print.attribute.standard.JobPriority;
import javax.swing.table.TableModel;
import javax.swing.text.TabSet;
public class Main {public static void main(String[] args) throws IOException  {
Scanner sc=new Scanner(System.in);
BufferedReader br1=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1=new PrintWriter(System.out);
int a=sc.nextInt();
int b;
ArrayList<Integer> al1=new ArrayList<>();
for(b=0;b<a;b++) {int c=sc.nextInt();if(al1.size()==0) {al1.add(c);}if(c>al1.get(al1.size()-1)) {al1.add(c);}else {int d=Collections.binarySearch(al1,c);if(d<0) {int e=(-1)*d-1;al1.set(e, c);}}
}
System.out.println(al1.size());}}