IT-garden

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

import sys
import copy
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=list(map(int,input().split()))

dp=[1]* n
c=copy.deepcopy(a)

for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]+1:
            dp[i]= dp[j]+1
            c[i] = max(c[i],c[j]+a[i])
        
print(max(c))

가장 긴 증가하는 부분수열의 알고리즘과 같게 만들고 수열의 합을 기록하는 배열을 하나 추가합니다.
a[i] > a[j] and dp[i] < dp[j]+1 조건이 만족하면 가장 값이 큰 경우를 배열 c에 넣습니다.

백준 알고리즘 11055번 : www.acmicpc.net/problem/11055