백준 12015. 가장 긴 증가하는 부분수열2, 3

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

 

가장 긴 증가하는 부분수열(https://tose33.tistory.com/18) 문제와 같지만 n의 최댓값이 100만으로 기존의 풀이인  O(N^2)으로는 풀 수 없다. 

 

벡터를 하나 만든후에, 주어진 값들을 탐색하면서 해당 값이 백터의 back() 값 보다 크다면 벡터에 푸쉬해주고, 

작거나 같다면 lower_bound() 함수로 주어진 값보다 크거나 같은 원소의 위치를 찾아 해당 위치에 삽입한다.

이렇게 주어진 수 보다 크거나 같은 값의 위치에 삽입하는 이유는 삽입되는 값이 이미 있던 값 보다 작고, 

길이가 같을때 더 작은 값이 들어가는것이 이후에 더 긴 증가하는 부분 수열을 만드는데 무조건 유리하기 때문이다. 

 

 

---

https://www.acmicpc.net/problem/12738

12738번: 가장 긴 증가하는 부분 수열 3

 

그냥 똑같은 문젠데 값의 범위가 위 문제는 양수범위고, 이 문제는 음수도 포함이다.

따라서 처음에 ans 벡터에 삽입하는 최솟값이 -10억 미만의 수이면 된다.