11055 - 가장 큰 증가하는 부분 수열

 

---

 

문제

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

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

 

풀이

가장 긴 증가하는 부분 수열과 비슷한 문제이다.

단 차이점은, 증가하는 부분 수열중 합이 가장 큰 값을 반환해야하는 것이다.

 

이 문제 또한 특정 인덱스에서 앞을 순회하면서,

1) 나보다 값이 작다면

2) 갱신되는 값이 더 크다면

갱신해준다. 라는 플로우를 따르면 된다. 

 

식으로 나타내면  D[i] = max(D[i], D[j] + arr[i]) 

(점화식 배열인 D[i] 는 i 까지 증가하는 수열의 가장 큰 합이 들어가있다. )

 

코드

l = int(input())
arr = list(map(int, input().split()))
s = [0] * 1001
for i in range(l):
    s[i] = arr[i]
for i in range(1,l):
    for j in range(i):
        if arr[j] < arr[i]:
            s[i] = max(s[i],s[j] + arr[i])

print(max(s))

 

후기

로직을 처음부터 생각하지 않고, 가장 긴 증가하는 수열 코드를 이리저리 만져서 풀려다가 오히려 헤맸다.

문제를 처음부터 천천히 접근하면서 생각하고 푸는 습관을 기르자.