CodeAngie

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. 풀이 DP를 사용하여 LIS를 구하는 기존 문제에 부분 수열의 길이뿐만 아니라 부분 수열을 요소까지 출력하는 문제이다. 따라서 증가하는 부분 수열의 요소를 담는 것을 함께 구현해야 한다. 증가하는 부분 수열의 요소를 담는 리스트를 생성하고 dp가 증가할 때 함께 업데이트 되도록 한다. 알고리즘 n과 a 수열을 입력받는다. 1로 초기화된 dp를 생성한다. 부분 수열의 요소를 담을 b 리스트를 생성한다. A 수열에서 뒤의 요소가 앞의 요소보다 크고 부분 수열의 길이도 더 길어질 때, 부분 수열의 길이를 업데이트 하면서 부분 수열의 요소도 업데이트 해준다. 가장 긴 부분 수열의 길이를 찾아 출력하고, 해당 위치와 동일한 부분 수열의..