Longest Ordered Subsequence
time limit per test 2 second memory limit per test 256 megabytes
A numeric sequence of ai is ordered if a1 < a2 < … < aN. Let the subsequence of the given numeric sequence (a1, a2, …, aN) be any sequence (ai1, ai2, …, aiK), where 1 <= i1 < i2 < … < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).
Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

传送门：POJ2533

Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Sample Input\

1
2
7
1 7 3 5 9 4 8

Sample Output

1
4

题解

传统O(n^2)是过不了的
## TLE code:(不包含输入类) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.io.*;  
import java.util.*;  
public class Main {  
    public static void main(String[] args) {  
        int[]shu={1,2,3,4,1,9,8};  
        System.out.println(lcs_n2(shu));  
        System.out.println(lcs_n2(shu));  
    }  
    public static int lcs_n2(int[] shu){        //n^2算法  
        int[] dp=new int [shu.length];  
        dp[0]=1;  
        for(int i=1;i<shu.length;i++){  
            dp[i]=1;  
            for(int j=0;j<i;j++){  
                if(shu[j]<shu[i]&&dp[j]>dp[i]){  
                    dp[i]=dp[j];  
                }  
            }  
            dp[i]=dp[i]+1;  
        }  
        int max=-1;  
        for(int i=0;i<shu.length;i++){  
            if(dp[i]>max){  
                max=dp[i];  
            }  
        }  
        return max;  
    }  
    //nlogn以后再填  
}
O(nlogn)做法: 多一个记录数组，遍历第一遍数组时，对每个数字进行判断，如果它比记录数组中最后一位还大，那就加入到记录数组中，否则用二分查找在记录数组中找到比它大的最小的下标，把那个下标的值更新为它。最后记录数组的长度就是LIS的长度
## AC code:(不包含输入类) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.*;  
public class Main {  
    public static void main(String[] args) {  
        Scanner sc= new Scanner(System.in);  
        int []shu;  
        while(sc.hasNext()){  
            int n=sc.nextInt();  
            shu=new int [n];   
            for(int i=0;i<n;i++){  
                shu[i]=sc.nextInt();  
            }  
            ArrayList<Integer>list=new ArrayList<Integer>();  
            for(int i=0;i<n;i++){  
                if(list.isEmpty()){  
                    list.add(shu[i]);  
                }  
                else{  
                    if(shu[i]>list.get(list.size()-1)){  
                        list.add(shu[i]);  
                    }  
                    else{  
                        int index=find(list,shu[i]);  
                        list.set(index, shu[i]);  
                    }  
                }  
            }  
            int jg=list.size();  
            System.out.println(jg);  
        }  
    }  
    public static  int find(ArrayList<Integer> list,int temp){   //二分查找降低复杂度  
        int start=0;  
        int end=list.size()-1;  
        while(start<end){  
            int mid=(start+end)>>1;  
            if(list.get(mid)<=temp){  
                start=mid+1;  
            }  
            else{  
                end=mid;  
            }  
        }  
        return start;  
    }  
}