隔了五天，感觉有了进一步的理解

题目描述

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N
第二行包含 N个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。
数据范围

1≤N≤100000 −109≤数列中的数≤109

样例

7
3 1 2 1 8 5 6

算法思想

思想就是利用一个数组f，存储一个长度为i的严格上升子序列的最后一个元素的最小值

这个题目就是一个最长上升子序列的优化问题，优化的主要思想就是贪心+二分
贪心主要就是指对给定的所有的元素进行一遍查找，给每一个数字找一个当时可以存储的位置

也就是第一次存在下标位1的地方，当第二个值来的时候，如果比第一个数字小，那么更新第一个数字
否则的话就把他放到第二个位置。
那么对于f数组的长度达到一个长度的时候我们肯定不可以一个元素一个元素的寻找，这时候就需要用到了二分

二分的使用，对于当前的一个数字x,我们需要在数组中找到一个合适的位置，什么样的位置算合适呢？

这样每次我们需要寻找一个长度为i+1的严格上升子序列的问题的时候，需要找一个大于长度为i的
子序列的末尾元素的最小值即可

代码

package dp;

import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class 最长上升子序列II {

    /**
     * @param args
     * @throws IOException 
     * @throws NumberFormatException 
     */
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(bufferedReader.readLine());
        int f[]=new int [n+1];
        int a[]=new int [n];
        int x=0;
   String p[]=bufferedReader.readLine().split(" ");
   for(int i=0;i<n;i++){
       a[i]=Integer.parseInt(p[i]);
   }
     int len=0;
     for(int i=0;i<n;i++){
           x=a[i];
           int l=0;
           int r=len;
           while(l<r){
             int mid=l+r>>1;
             if(f[mid] <x){
                 l=mid+1;
             }else {
                r=mid;
            }
         }
           len=Math.max(len, r+1);
           f[r]=x;
          // System.out.println(l);
          // System.out.println(Arrays.toString(f));
     }
     System.out.println(len);
    }

}