Computer Science/Algorithm
[Baekjoon] DP - 11055 가장 큰 증가하는 부분 수열
ddu0422
2023. 9. 25. 07:47
문제
11055번: 가장 큰 증가하는 부분 수열
수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는
www.acmicpc.net
풀이
"""
가장 큰 증가하는 부분 수열의 합
"""
import sys
from copy import deepcopy
n = int(sys.stdin.readline().rstrip())
numbers = [0] + list(map(int, sys.stdin.readline().rstrip().split()))[:n]
def solution(a):
d = deepcopy(a)
for i in range(2, len(a)):
for j in range(1, i):
if a[i] > a[j] and d[i] < d[j] + a[i]:
d[i] = d[j] + a[i]
return max(d)
print(solution(numbers))
채점 결과
