前言
动态规划这类问题一直是大家学习算法，平时练习中遇到的最难的问题之一。其中有一类问题是线性的，也叫他线性DP。今天我们一起来分析一下最长上升子序列I。
题目信息
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
注意：这里的子序列要求是严格单调递增的。例如 1，2，3，4。不能是1，1，2，3，4。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
本题数据范围：
1≤N≤100000， ?109≤数列中的数≤109
算法题的主要目的还是在能做出来的前提下，优化算法的时间复杂度，所以题目的数据范围就是一个很需要关注的点了。
样例
输入：
7 3 1 2 1 8 5 6
输出:
4
思路
原分析思路作者：闫学灿。网站AcWing
可能只有一个图看得不是很懂。给大家举一个例子。
3 1 2 1 8 5 6
解释：
集合：状态表示的集合的意思就是以某个数为结尾的集合。比如8这个数的集合就包括，{1,8}，{3，8}，{2,8}，{1,8}；
属性：但是f[i]是一个具体的值。这个值就表示在这些集合中最长的集合长度。这里就是2了。
状态计算: 因为每个集合都是以第i个数为结尾的，那么就说明每个数都包含了i这个数。下面的椭圆表示的是将这些集合以第i-1个数分成若干类。
第一种：第i-1个数是0，也就是说子序列的长度是1，他没有第i-1个数
第二种：第i-1个数是1，它的最长上升子序列的长度就是 i-1+ i,即f[1]+1
第三种：第i-2个数是2，它的最长上升子序列的长度就是 i-2+ i,即f[2]+1
…
第i-1种：第i-1个数是i-1，它的最长上升子序列的长度就是 i-1+ 1,即f[i-1]+1
需要注意的是这些序列不一定都存在，因为是最长上升子序列，所以还需要满足，a[i]>a[j]。因为i是最后一个数，j一定是比他小的。
好了，思路完了就可以开始写代码了。
代码
import java.util.Scanner;
public class Main {
static int N=1010;
//题目给的子序列
static int a[]=new int[N];
//状态表示的数组
static int f[]=new int[N];
public static void main (String[] args) {
Scanner sc=new Scanner (System.in);
int n=sc.nextInt ();
for (int i = 1 ; i <=n ; i++) {
a[i]=sc.nextInt ();
}
//f[i]表示最长上升子序列的最大长度
for (int i = 1 ; i <=n ; i++) {
f[i]=1;
//f[i]=1 这时只有i一个数，所以f[1]=1;
for (int j = 1 ; j <i ; j++) {
if(a[j]<a[i]){
f[i]=Math.max (f[i],f[j]+1);
}
}
}
//求出所有f的集合后，在遍历一遍f，求出最长的子序列的长度。
int res=0;
for (int i = 1 ; i <=n ; i++) {
res=Math.max (res,f[i]);
}
System.out.println (res);
}
}