백준 13398번 파이썬 문제풀이(DP - 연속합 2)

---

*개인적으로 연속합 1 문제에서 코드가 한줄 추가되는 거지만 생각하기가 굉장히 까다로웠다. 우선 dp를 2중 리스트로 선언하여 2가지 dp를 비교를 하면서 큰 값을 찾는 문제이다.

우선 dp를 다음과 같이 초기화 해야한다.

dp : 연속합을 구하기 위한 누적합

- dp[0][i] : 특정 원소를 제거하지 않은 경우
- dp[1][i] : 특정 원소를 제거한 경우

 

N이 1보다 클 경우 dp를 찾으면 되는데 

1. 특정 원소를 제거하지 않은 경우

dp[0][i] = max(dp[0][i - 1] + input_array[i], dp[i]) : 아무런 원소를 제거하지 않고 일반적인 연속합으로 구하는 경우이다.

 

2. 특정 원소를 제거하는 경우

dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + + input_array[i]) : 다음의 두가지 사항중 큰 값을 대입

 - i번째 원소를 제거하는 경우 -> 위에서 구한 i - 1 번째 연속 합의 최대값을 그대로 대입

 - i번째 이전의 원소를 이미 제거하여 이전에 구해놓은 dp값에 현재 i 값을 더해주는 경우 -> i번째 이전의 원소를 제거한 연속합 값 + 현재 원소 i 값 

 

코드

import sys

input = sys.stdin.readline

N = int(input())
input_array = list(map(int, input().split()))
dp = [[x for x in input_array] for _ in range(2)]

for i in range(1, N):
    dp[0][i] = max(dp[0][i - 1] + input_array[i], dp[0][i])
    dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + input_array[i])

print(max(max(dp[0]), max(dp[1])))