[S2] 1912 연속합

유형: dp

문제를 보고 누적합 개념을 떠올려서 풀었다.

점화식이 바로 떠오르지 않아서 난감했다.

• 추가로 dp 점화식을 떠올릴 때는 단계별로 써보는게 짱인듯 하다.

• 실제로는 더 간단한 점화식으로도 풀 수 있었다.

  • https://data-marketing-bk.tistory.com/52

해결 시간: 1시간 14분

제출 코드

N = int(input())
arr = list(map(int, input().split()))

# 누적합 배열
sum = [arr[0]]
for n in arr[1:]:
    sum.append(sum[-1] + n)

# dp[i]: 인덱스 i까지 고려했을 때 최댓값
dp = [-float('inf') for _ in range(N)]
dp[0] = arr[0]
sum_min = arr[0] # 누적합 배열의 최소
for i in range(1, N):
    dp[i] = max(
        sum[i], # ~ i 까지의 부분합
        sum[i] - sum_min, # sum_min ~ i까지의 부분합
        dp[i-1]
    )
    sum_min = min(sum_min, sum[i])
print(dp[-1])