백준 13398번 : 연속합 2 in Python

13398번: 연속합 2

 

www.acmicpc.net

이 문제는 n개의 정수로 이루어진 임의의 수열에서 가장 큰 연속합을 구하는 문제이다. 단, 수열에서 수를 하나 제거할 수 있다.

우선 연속합을 구하는 방법을 생각해보자. 우선 N개의 정수로 이루어진 수열에서 N-1개의 정수로 이루어진 수열과 1개의 정수로 이루어진 수열로 나눈다. 그리고 N-1개의 정수로 이루어진 수열에서 구한 연속합의 최댓값을 구했다고 가정하자. 이때 1개의 정수로 이루어진 수열에서 연속합의 최댓값은 그 정수와 같다. 여기까지 하면 N-1개의 정수로 이루어진 수열과 1개의 정수로 이루어진 수열의 연속합의 최댓값을 구한 상태로, 여기에다가 N-1개의 정수로 이루어진 수열과 1개의 정수로 이루어진 수열에 걸쳐있는 연속합의 최댓값까지 고려한다면 N개의 정수로 이루어진 수열의 연속합의 최댓값을 구할 수 있다.

이를 N = 2일 때부터 N = n일 때부터 계산하면 전체 수열 내에서 구할 수 있는 연속합의 최댓값을 구할 수 있다. 

이제 이를 구체적으로 구현하고 이 구현 과정에서 정수를 하나 제거하는 경우도 고려해보자. 우선 2*n 크기의 행렬을 만든다. dp[0]에는, 수열 내 i번째 원소가 마지막인 연속하는 수열의 연속합의 최댓값을 i번째 entry에 저장한다. dp[1]에는, 위와 비슷하지만 수열 내에서 하나의 정수를 제외한 경우를 고려한다. 초기값으로는 dp[0][0]은 수열의 첫 번째 원소, dp[1][0]은 -INF로 한다.

이제 수열의 연속합의 최댓값을 저장하는 변수인 maxSum을 정의하고 초기값을 수열의 첫 번째 원소로 한다. 그 다음 i = 1부터 i = n-1까지 순회하면서 dp[0][i]는 dp[0][i-1] + seq[i]와 seq[i] 중 더 큰 값으로, dp[1][i]는 dp[0][i-1]과 dp[1][i-1] + seq[i] 중 더 큰 값으로 한다. 즉, dp[0][i]는 i-1개의 정수로 이루어진 수열과 1개의 정수로 이루어진 수열에 걸쳐있는 수열의 연속합의 최댓값과, 1개의 정수로 이루어진 수열의 연속합 중 더 큰 값으로 한다. dp[1][i]는 i번째 정수를 제외했을 때와 이전에 정수를 이미 제외한 경우 중 더 큰 값으로 한다. 그 다음 maxSum은 dp[0][i]와 dp[1][i], maxSum 중 가장 큰 값으로 한다.

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
n = int(input())
seq = list(map(int, input().split()))
dp = [[-sys.maxsize]*n for _ in range(2)]
dp[0][0] = seq[0]
maxSum = seq[0]
for i in range(1, n):
    dp[0][i] = max(dp[0][i-1] + seq[i], seq[i])
    dp[1][i] = max(dp[0][i-1], dp[1][i-1] + seq[i])
    maxSum = max(maxSum, dp[0][i], dp[1][i])
print(maxSum)