가장 큰 증가하는 부분 수열
면접 대비시간 제한1초메모리 제한256 MB
순서를 유지하며 더 큰 원소만 골라 합이 가장 커지는 증가 부분수열의 합을 구합니다.
문제
수열 A가 주어진다. A의 증가하는 부분 수열 중에서 원소의 합이 가장 큰 것을 찾아 그 합을 구하는 프로그램을 작성하시오.
부분 수열은 A에서 원소를 몇 개 골라 원래 순서대로 늘어놓은 수열이고, 증가하는 부분 수열은 고른 원소가 앞에서 뒤로 가면서 엄격하게 커지는 부분 수열이다. 예를 들어 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}에서 1, 2, 50, 60을 고르면 합이 113이 되고, 합이 이보다 큰 증가하는 부분 수열은 없다.
입력
첫째 줄에 수열 A의 크기 N이 주어진다. (1 ≤ N ≤ 1,000)
둘째 줄에 수열 A를 이루는 Ai가 공백으로 구분되어 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.