题目描述：

最长递增子序列（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);
    }
}