[Gold V] 연속합 2 - 13398

문제 링크

성능 요약

메모리: 38964 KB, 시간: 176 ms

분류

다이나믹 프로그래밍

문제 설명

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

---

풀이

아이디어

여러 시도 끝에 점화식 비스무리한 것을 만들어냈다

그런데 아무리 난리를 쳐봐도 약간의 반례와 구현에 상당한 애를 먹었다.
따라서 다른 사람의 아이디어를 따라하기로 했다.
2차원 리스트로 하나는 부분합이고, 하나는 해당하는 인덱스의 값을 뺏을 때 최댓값인 경우이다.

N = int(input())
S = [0] + list(map(int, input().split()))
sums = sum(S)
flag = False
def solve(n):
    print(n)
    global flag
    if n == 0:
        return 0
    
    if (k:=S[n] + solve(n-1)) > (m:=sums - sum(S[:n])):
        return k
    
    else:
        return m

print(solve(N))

아주 엉망이다.

이 블로그에 따르면 이 문제는 간단한 아이디어를 통해 풀 수 있다.
현재 값을 기준으로 좌측의 연속합, 우측의 연속합을 더하면 현재 값을 제외한 결과값 중 최대의 값을 구할 수 있게 된다.

코드

n = int(input())
a = list(map(int, input().split()))
dp1 = [0 for _ in range(n)]
dp2 = [0 for _ in range(n)]
dp1[0] = a[0]
dp2[0] = -int(1e8)
result = -int(1e8)
for i in range(1, n):
    dp1[i] = max(a[i], a[i]+dp1[i-1])
    dp2[i] = max(dp1[i-1], dp2[i-1]+a[i])

for i in range(n):
    result = max(result, dp1[i], dp2[i])
print(result)

---

회고

탑 다운으로는 너무 헷갈려서 직관적인 바텀업으로 풀이하였다.
너무 오래 고민해서 정답을 참조한 문제.