최대증가부분수열

입력 받은 정수배열에서 최대증가부분수열을 반환하는 함수를 작성합니다.

부분수열의 각 원소는 배열안에서 반드시 인접하지는 않지만 배열에 나타나는 것과 동일한 순서로 구성된 숫자 집합입니다. 예를 들어 [1, 3, 4]는 배열 [1, 2, 3, 4]의 부분수열을 형성하고 마찬가지로 [2, 4]도 부분수열입니다.

입력 받은 배열과 배열의 각 하나의 숫자는 입력 받은 배열의 유효한 부분수열 입니다.

최대증가부분수열은 단 한 개만 있습니다.

예제 1

입력

arr = [5, 7, -24, 12, 10, 2, 3, 12, 5, 6, 35, 1]

출력

[-24, 2, 3, 5, 6, 35]