[Python]13398. 연속합 2

https://www.acmicpc.net/problem/13398

13398번: 연속합 2

---

 

하나 제거할 때의 연속합의 최대값이란, 

특정 시점 (i) 를 기준으로 앞에서부터의 연속합 중 (i-1) 위치와  뒤에서부터의 연속합 중 (i+1) 위치의 연속합의 합이다.

다시말해, dp2[i] = dp[i-1]+dr[i+1], 단 1<=i<=n-2.

 

Step1. 우선 기본적인 앞에서 부터의 연속합을 구한다 (dp)

Step2. 역순으로 뒤에서 부터의 연속합을 구한다 (dr)

Step3. dp2[i] = dp[i-1]+dr[i+1]    (1 <= i <= n-2)

Fin. 그냥 연속합의 최대(max(dp))와 하나 제거할 때 연속합의 최대(max(dp2)를 비교해 최대값을 출력한다. 

 

n = int(input())
a = list(map(int, input().split()))
 
dp = [0]*(n)
dp[0] = a[0]
for i in range(1,n):
    dp[i] = max(dp[i-1]+a[i], a[i])
 
dr = [0]*(n)
dr[n-1] = a[n-1]
for i in range(n-2, -1, -1):
    dr[i] = max(dr[i+1]+a[i], a[i])
    
dp2 = [0]*(n)
for i in range(n):
    if i == 0 or i == n-1:
        dp2[i] = a[i]
        continue
    dp2[i] = dp[i-1]+dr[i+1]
 
answer = max(max(dp), max(dp2))
print(answer)