🐢 연속합 2

1. 문제 링크

13398번: 연속합 2

2. 코드

Python3 38828KB 6168ms

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

💙 출력
첫째 줄에 답을 출력한다.
"""

# n 개의 정수
n = int(input())
# n 개로 이뤄진 수열
array = list(map(int, input().split()))

# dp 2차원 배열에 제거, 제거하지 않는 것
dp = [ [0] * (n + 1) for _ in range(2)]

# 제거하지 않은 dp
dp[0][0] = array[0]
# 첫 시작
answer = array[0]

# 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)
for i in range(1, n) :
    # 최대값 (그 전 + 현재 , 현재)
    dp[0][i] = max(dp[0][i - 1] + array[i], array[i])
    # 최대값 (현재 제거, 이전 제거 + 현재)
    dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + array[i])
    # 제거x, 제거0, 처음에는 첫 숫자 (그후에 갱신)
    answer = max(dp[0][i], dp[1][i], answer)

print(answer)

3. 해설

• dp 2차원 배열로 만들어서 제거, 제거하지 않은 경우를 만듦
  • 그 전 + 현재, 현재
  • 현재 제거, 그 전 제거 + 현재
  • 갱신한다