boj 14003

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 1. Logic - 기본 구성은 가장 긴 증가하는 부분수열 2, 3과 똑같다. 하지만 여기서는 역추적을 통해 LIS가 어떻게 구성되었는지 경로를 출력해야한다. 경로를 갱신해 줄 때 아무값이나 막 넣어주면 안되기 때문에 첫번째로 LIS인 수열에 대해서 입력해준다. 즉 이전에 들어간 숫자보다 더 큰 숫자가 나올경우 경로를 갱신해준다. 만약 이전에 들어간 숫자보다 작은 숫..