[BOJ] 11053번: 가장 긴 증가하는 부분 수열

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

다이나믹으로 적당히 잘 구현하면 O(N^2)의 시간복잡도로 구할 수 있습니다. (D[i] : 0~i에서 LIS의 길이일 때 D[n] = max D[i] for all i = 0~n-1 s.t. A[n] > A[i]) N이 별로 크지 않아 그냥 O(N^2)로 해결했습니다.

참고로 binary search나 segment tree를 활용하면 O(NlgN)으로 구할 수 있습니다. NlgN이 lower bound인지는 잘 모르겠습니다.(아마 맞을텐데 수학적으로 증명이 된 사항인지는 모릅니다.)

https://github.com/encrypted-def/BOJ/blob/master/11053.cpp