[백준] 13398번(연속합 2)

백준 13398번

최종 제출 코드

n = int(input())
array = list(map(int, input().split()))

dp = array[:]
dp2 = array[:]

for i in range(1, len(array)):
  dp[i] = max(dp[i-1]+array[i], dp[i])
  dp2[i] = max(dp2[i-1]+array[i], dp[i-1])
    
print(max(max(dp),max(dp2)))

.
◼ 연속합을 구하는 풀이는 연속합 문제와 동일

• dp에는 i번째 원소까지의 부분합 중 가장 큰 값이 저장된다.

.
◼ 원소를 1개 삭제할 때의 부분합을 구하는 과정이 필요

• 원소를 삭제하지 않는 경우와 1개 삭제할 경우의 값을 구하는 배열이 각각 필요
• 원소를 삭제하지 않는 경우의 값을 구하는 배열 dp를 우선 업데이트
• 현재 인덱스가 i라고 했을 때, 원소를 1개 삭제할 경우의 값을 구하는 배열 dp2는 dp2[i-1] + array[i]와 dp[i-1] 중 큰 값을 dp2[i]에 저장한다.
• 즉, i번째 원소 전에 존재하는 원소 1개를 삭제하는 경우가 이득인지 i번째 원소를 삭제하는 경우가 이득인지를 판단한다.
• i번째 원소 전에 존재하는 원소를 삭제하는 경우가 이득이면 i번째 원소는 삭제해서는 안됨으로 dp2[i-1] + array[i]를 해준다.
• i번째 원소를 삭제하는 경우가 이득이면 array[i] 값이 반영되지 않은 dp[i-1]를 저장한다.

.
◼ 원소를 1개 삭제하는 경우와 삭제하지 않는 경우 중 큰 값을 출력