Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
[VOJ] Mã nguồn #203 - LIS [JAVA]
Ngày: 24-02-2011
Cập nhật: 21-04-2011
Người gửi: doremon
Ngôn ngữ: Java
Xem: 664

Điểm: 5.0/5 (9 Phiếu)


// Author: Bùi Thị Liên - FPT University
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.*;
 
public class LIS{
	static BufferedReader jin=new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter jout=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	static StringTokenizer token;
	static String nextToken() throws IOException{
		while (token==null||!token.hasMoreTokens()){
			token=new StringTokenizer(jin.readLine());
		}
		return token.nextToken();
	}
	static int nextInt() throws IOException{
		return Integer.parseInt(nextToken());
	}
	static long nextLong() throws IOException{
		return Long.parseLong(nextToken());
	}
	static double nextDouble() throws IOException{
		return Double.parseDouble(nextToken());
	}
	static String nextString() throws IOException{
		return nextToken();
	}
	static int maxn=30000+10;
	static int i,j;
	static int n;
	static int[] a=new int[maxn];
	static int[] startof=new int[maxn];
	static int find(int u){
		int l=0,r=n+1,mid;
		while (l+1<r){
			mid=(l+r)>>1;
			if (a[startof[mid]]<u) l=mid;else r=mid;
		}
		return l;
	}
	static void enter() throws IOException{
		n=nextInt();
		for (i=1;i<=n;i++) a[i]=nextInt();
		a[0]=1000000000;
		startof[0]=0;
	}
	static void solve() throws IOException{
		int k;
		int res=0;
		for (i=1;i<=n;i++){
			k=find(a[i]);
			k++;
			if (k>res) res=k;
			if (a[startof[k]]>a[i]) startof[k]=i;
		}
		jout.print(res);
	}
	public static void main(String[] args) throws IOException{
		enter();
		solve();
		jout.close();
	}
}