[백준] 12015 가장 긴 증가하는 부분 수열 2 [자바]

 

 

---

https://st-lab.tistory.com/285?category=948182 

[백준] 12015번 : 가장 긴 증가하는 부분 수열 2 - JAVA [자바]

 

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
	static long ans = 0;
 	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();		
		//StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(br.readLine());
		int[] seq = new int[N];
		int[] LIS = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < N; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}
		
		LIS[0] = seq[0];
		int lengthOfLIS = 1;
		
		for(int i = 1; i < N; i++) {
			
			int key = seq[i];
			
			if(LIS[lengthOfLIS - 1] < key) {
				lengthOfLIS++;
				LIS[lengthOfLIS - 1] = key;
			}
			else {
				int lo = 0;
				int hi = lengthOfLIS;
				
				while(lo < hi) {
					int mid = (lo + hi) >> 1;
					
					if(LIS[mid] < key) {
						lo = mid+1;
					}
					else {
						hi = mid;
					}
				}
				
				LIS[lo] = key;
			}
		}
		System.out.println(lengthOfLIS);
 	}
}