题目描述：
最长递增子序列（LCS）
给定一个序列 An = a1 ,a2 , ... , an ，找出最长的子序列使得对所有 i < j ，ai < aj 。求出这个子序列的长度。
输入描述：
输入的序列
输出描述:
最长递增子序列的长度
输入示例：
1 -1 2 -2 3 -3 4
输出示例：
4
题目分析：
这道题呢，也是一道动态规划的题目。我们定义dp[i]为以i为结尾的最长递增子序列的长度。初始状态是dp[i]=1，状态转移方程为dp[i]=Math.max(max,dp[j]+1),0<=j<i。也就是说再确定dp[i]时，我们需要j从0到i-1去遍历一遍。为什么是需要遍历一遍呢，举个栗子来看一下就一目了然啦。比如输入序列为{1,2,3,4,2,6}，很显然dp[5]=5，而dp[4]=2，dp[3]=4。所以在求dp[5]时，我们是需要遍历0~4的，而不是直接取dp[4]。原因是我们定义dp[i]为以i为结尾的最长递增子序列的长度，它是包含i的。emmm...好像解释的不太好，还是看代码吧。代码如下~
代码实现：
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.lang.Math;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String input=sc.nextLine();
List<Integer> nums=new ArrayList<Integer>();
for(String num: input.split(" ")){
nums.add(Integer.parseInt(num));
}
int[] dp=new int[nums.size()];
for(int i=0;i<nums.size();i++){
int max=1;
for(int j=0;j<i;j++){
if(nums.get(i)>nums.get(j)){
max=Math.max(max,dp[j]+1);
}
}
dp[i]=max;
}
int ret=0;
for(int i=0;i<dp.length;i++){
ret=Math.max(ret,dp[i]);
}
System.out.println(ret);
}
}
