[백준][13398] 연속합 2

• Problem Link : https://www.acmicpc.net/problem/13398

문제

• 크기가 n개의 정수로 이루어진 임의의 수열 주어진다.
• 부분 수열의 합 중에서 최대값을 구한다.
• 이 때 수를 하나 제거할 수 있다. (제거하지 않아도 된다.)

입력

• 첫째 줄, n이 주어진다.
• 둘째 줄, n개의 정수로 이루어진 수열이 주어진다.

출력

• 첫째 줄, 부분 수열의 합의 최대값을 출력한다.

풀이

수를 제거하지 않았을때 부분 수열의 최대값은 앞의 수열에 자신이 들어가거나, 자신만 들어가거나 하는 경우 두 가지가 있다.
수를 제거했을때의 부분 수열 최대값은 수를 제거하지 않은 부분 수열의 최대 합에 자신이 들어가거나, 자신만 들어가거나 하는 경우 두 가지가 있다. 위 두가지 경우에 대해 그림을 그려서 규칙성을 찾아 최대값을 구해보자.

한 번의 step 당 같은 화살표 두 개는 해당 화살표가 연결된 것끼리 더해서 화살표 두 개 중 최대값을 선택하는 과정이다.

1. 수를 제거하지 않을 때 최대값
   수를 제거하지 않고 부분수열의 최대의 합을 구하는 것은 다음 그림과 같다.

• 앞의 수열에 자신이 들어간 것과 그냥 자신만 들어간 수열 중 큰 값을 선택

• 첫째 줄 : 입력 원소
• 둘째 줄 : 수를 제거하지 않을때 최대 부분 수열 구하는 과정

2. 수를 하나 제거할 수 있을때 최대값
   만약에 하나의 수를 빼고 최대값을 구해보자.

• 하나도 제거하지 않은 수열에 자신이 제거되서 (0으로 변화) 들어간 것과 이미 하나 뺀 것에 자신이 들어가거나하는 경우 두 가지가 있다.
• 자기 자신만 들어가는 경우는 이미 위 1번 케이스에서 찾았기 때문에 별도로 비교하지 않는다. 최대값을 구할 때 수를 제거한 경우와 제거하지 않은 경우 모두 방문할 예정이기 때문이다.

• 첫째 줄 : 입력 원소
• 둘째 줄 : 수를 제거하지 않을 때 최대 부분 수열 구하는 과정
• 셋째 줄 : 수를 하나 제거할 때 최대 부분 수열 구하는 과정

각 케이스의 점화식을 아래와 같이 쓸수 있다.

이를 2차원 배열로 구현하면 아래 코드와 같다.

코드

import sys

input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))

dp = [[a[0], a[0]]]
for i in range(1, n):
    dp.append([max(dp[i - 1][0] + a[i], a[i]), max(dp[i - 1][0], dp[i - 1][1] + a[i])])

ans = a[0]
for i in range(n):
    ans = max(ans, max(dp[i][0], dp[i][1]))
print(ans)