[백준 11055] 가장 큰 증가하는 부분 수열

11055번: 가장 큰 증가 부분 수열

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

https://www.acmicpc.net/problem/11055

Tip

•

가장 긴 증가하는 부분 수열 문제와의 차이점과 기본적으로 유사

•

차이점은 DP 테이블 초기화시, 입력받은 수열을 그대로 가져와서 넣어주는 작업 필요.

◦

1로 전부 초기화가 아닌, 수열의 각각의 인덱스 데이터는 기본적으로 더해진 값으로 초기화

풀이 소스 코드

import sys
si = sys.stdin.readline
# n과 수열 입력
n = int(si())
array = list(map(int, si().split()))
# 증가하는 부분 수열의 합을 담을 DP 테이블
d = array[:]
for i in range(1, n):
for j in range(i):
if array[i] > array[j]:
d[i] = max(d[i], d[j] + array[i])
# 가장 큰 증가하는 부분 수열 길이 출력
print(max(d))
Python