[BOJ] 11055 가장 큰 증가 부분 수열을 O(N^2)이 아니라 O(NlogN)으로 구하기

문제 주소: https://www.acmicpc.net/problem/11055

문제 푼 이유: 예전에 N^2으로 풀었지만, 오늘 LIS를 세그먼트 트리로 구하면서 이걸 가장 큰 증가 부분 수열에도 적용할 수 있을 거라 생각했다.
막상 구글링해 보니 다들 N^2이었고, 맞은 사람들 코드를 봐도 N^2만 있었다. 그래서 직접 해봤다.

풀이 방법: 일반적인 dp 풀이법으로 O(N^2)으로 구할 수 있다.
하지만, 세그먼트 트리를 활용하면 O(NlogN)으로도 구할 수 있다.

문제에 얽힌 슬픈 이야기: N의 크기가 작아서 N^2으로도 0ms가 나온다..

해당 코드는 아래 BOJ 코드 공유 기능 주소를 통해 확인할 수 있다.

http://boj.kr/81b5c5159068496e9208efd4dc462843