[🥇5 / 백준 13398 / 파이썬] 연속합 2

 

13398번: 연속합 2

 

문제

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보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

 

예제 입력 10 10 -4 3 1 5 6 -35 12 21 -1

예제 출력 54

 

풀이

 

중간에 수를 제거하지 않은 경우, 제거한 경우 이렇게 2차원의 dp 배열을 만들어 해결한다.

수열을 담은 리스트는 arr 이라고 칭하겠다.

 

dp[0][i] 는 i번째 까지의 연속합과 arr[i] 중 더 큰 것이 담긴다.

앞의 숫자가 모두 음수인 경우가 있는 경우에 유의해야 한다.

즉 -3 -5 -1 이란 수열이 들어왔을 경우 연속합보다 마지막 수 하나만 담는 것이 더 크기 때문에 위처럼 시행한다.

 

dp[1][i] 는 arr[i] 가 음수일 때 건너뛸 경우, 그리고 dp[1][i-1]에 현재 수를 더한 경우(연속합을 이어나가는 경우) 중 더 큰 것을 담는다.

 

따라서 점화식은 다음과 같다.

dp[0][i] = max(dp[0][i-1]+arr[i],arr[i])
dp[1][i] = max(dp[0][i-1], dp[1][i-1]+arr[i])

 

n = int(input())
arr = list(map(int,input().split()))
dp = [[-1000]*n for _ in range(2)]

ans = -1000
for i in range(n):
    dp[0][i] = max(dp[0][i-1]+arr[i],arr[i])
    dp[1][i] = max(dp[0][i-1], dp[1][i-1]+arr[i])
    ans = max(ans, dp[0][i], dp[1][i])
print(ans)