11055. 가장 큰 증가 부분 수열

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

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

가장 긴 증가하는 부분수열 문제와 비슷하지만 길이를 구하는게 아닌 가장 큰 수의 합을 구하는 문제. 

가장 긴 증가하는 부분수열 문제에서는 이전 숫자와 비교하면서 계속 길이를 갱신했다면 이번에는 더하면서 합을 갱신한다. 

각각 의 합을 갱신하면서 가장 큰 합도 계속 갱신한다. 

 

import sys
n = int(input())

s = [0] * n  # 합을 기록할 배열
a = [0] * n  # 수열 저장할 배열
a = input().split()

for i in range(n):  # str로 입력한 배열들 int로 변경
    a[i] = int(a[i])
    s[i] = int(s[i])

if n == 1:
    print(a[i])
    sys.exit()

"""
증가하는 가장 긴 수열과 비슷하게 a[i]와 a[j]를 비교하면서 a[j]가 더작은 
경우 중에서 가장 큰 s[j]와 a[i]를 더한값이 s[i]
"""
s[0] = a[0]  # 수열 첫번쨰의 합은 자기자신
res = s[0]
for i in range(1, n, 1):
    max_sum = 0
    for j in range(i):
        if a[j] < a[i]:
            max_sum = max(max_sum, s[j])

    s[i] = max_sum + a[i]  # s[i]값 갱신

    res = max(res, s[i])  # 가장 큰 값 갱신


print(res)

 

---

Solution

 

코드

d = [0] * 1001

n = int(input())
a = input().split()
for i in range(n): a[i] = int(a[i])

res = a[0]  # 요소가 하나일 경우에는 첫번째 값이 최대값이 되어야 한다.
for i in range(n):
    d[i] = a[i]  # 초기값은 '1'이 아니라 해당 요소의 값이어야 한다.
    for j in range(i):
        # 각각의 요소값을 함산하여 비교하여야 한다
        if a[j] < a[i]: d[i] = max(d[i], d[j] + a[i])
        res = max(res, d[i])

print(res)