가장 큰 감소 부분 수열
면접 대비시간 제한1초메모리 제한256 MB
주어진 수열에서 원소가 엄격히 감소하는 부분수열 중 합이 최대인 것의 합을 구해 출력한다.
문제
수열 A가 주어졌을 때, 감소 부분 수열 중 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5}인 경우 합이 가장 큰 감소 부분 수열은 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5}이고, 합은 186이다.
입력
첫째 줄에 수열 A의 크기 N(1 ≤ N ≤ 1000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다.(1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 합이 가장 큰 감소 부분 수열의 합을 출력한다.