[백준] 연속합2

출처:: www.acmicpc.net/problem/13398

분류:: dp

 

1. 문제 이해 및 해결과정

 1)누적합 이용 -> 실패

- 원래의 수 + 한 개 제거한 경우 100000+1 - n+1개의 리스트를 만들어 누적합 배열을 구한다.  - 누적합의 최대값과 최소값의 차를 뺀 것중 최대로 나오는 값을 구함 - 반례 1 -3

 2) dp

- dp[i] i까지 최대 연속합  - dp[0][i] : 왼쪽부터 i까지 최대 연속 합 - dp[1][i] : 오른쪽부터 i까지 최대 연속 합 => dp[0][i-1]+dp[1][i+1] =>i 번째 수를 제외한 최대 연속합

 

2. 풀이방법

  1. dp

#연속합 2
#https://www.acmicpc.net/problem/13398
import sys
sys.stdin = open("input.txt","r")
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
res=-1e9
dp=[[0]*n for _ in range(2)]
for i in range(n):
    dp[0][i]=a[i]
    dp[1][i]=a[i]
for i in range(1,n): #앞에서부터 최대 연속합 
    dp[0][i]=max(dp[0][i],dp[0][i-1]+a[i])
for i in range(n-2,-1,-1): #뒤에서부터 최대 연속합
    dp[1][i]=max(dp[1][i],dp[1][i+1]+a[i])
# print(dp[1])
res=max(dp[0]) #수를 빼지 않은 원본리스트
for i in range(1,n-1):
    res=max(res,(dp[0][i-1]+dp[1][i+1])) #a[i]를 제외한 최대 연속합
print(res)

 

3. 오답원인

 

4. 알게된 점