🧚‍♂️알고리즘🧚‍♂️ - 동적 계획법(DP) 3

골5

13398번: 연속합 2

연속된 수를 선택해서 구할 수 있는 가장 큰 합 구하기

중간에 하나 뺴도 됨

 

작은 문제로 나누기!

 

왼쪽에서부터 인덱스를 포함한 최댓값 구하기

오른쪽에서부터     ''

그럼 하나 뺀 최댓값 구하기 가능

wow--

from sys import stdin
N = int(stdin.readline())
nlist = list(map(int,stdin.readline().split()))

result = nlist[0]

#왼쪽으로부터의 최댓값 구하기 (수 하나 삭제용)
L = [0 for _ in range(N)]
L[0] = nlist[0]

for i in range(1, N):
    L[i] = max(L[i-1]+nlist[i], nlist[i])
    result = max(result, L[i]) #아무것도 빼지 않았을 때의 최댓값
    
#오른쪽부터의 최댓값 구하기
R = [0 for _ in range(N)]
R[N-1] = nlist[N-1]

for i in range(N-2, -1,-1):
    R[i] = max(R[i+1]+nlist[i], nlist[i])

#하나가 빠졌을 때 최댓값
for i in range(1,N-1):
    result = max(result, L[i-1] + R[i+1])

print(result)

연속된 것에서 어떤 값을 뺴야 할 때는

양쪽 두 부분으로 나눈 후에 합치는 것로 생각할 수 있다.

 

result 값 리스트에 있는 값으로 초기화하기