문제 설명수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.https://www.acmicpc.net/problem/14003 제한 사항 풀이문제를 요약하면 LIS를 구하는 것이다. 일반적인 dp를 이용한 LIS는 $O(N^2)$이기 때문에 시간 초과가 발생할 것이다.lower_bound를 사용하는 방법을 이용하면 $O(NlogN)$까지 줄일 수 있다.하지만 이 방법을 해당 문제에서 그대로 적용할 수 없다.왜냐하면 해당 방법은 배열을 뒤로 진행시키며 자신이 들어갈 위치의..
