LIS

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

12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이전까지 풀어봤던 LIS 문제들과 푸는 방법이 조금 다르다 기존LIS는 for문을 2번 돌려서 O(n^2) 시간안에 풀었다면 이번 문제는 수열의 크기가 N st){ int mid = (st + ed)/2; if(key > arr[mid]){ st = mid+1; } else{ ed = mid; } } return ed; } void solve(){ int cnt = 1; res.push_back(arr[0]); for(int i = 1; i