증가부분수열의 최대합

입력된 양의 정수 배열에서 증가하는 부분수열의 합계가 가장 큰 경우의 해당 부분수열을 반환하는 함수를 작성하세요.

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

주어진 배열과 배열의 단일 숫자는 주어진 배열의 유효한 부분수열 입니다.

부분수열의 가장 큰 합계는 하나만 있습니다.

예제 1

입력

arr = [10, 70, 20, 30, 50, 11, 30]

출력

[10, 20, 30, 50]
// 증가부분수열 [10, 20, 30, 50]의 합 110은 
// 다른 증가부분수열의 합 중에서 최대값입니다.