[DP] 백준 1912번 “연속합” Python 풀이

문제 링크

• https://www.acmicpc.net/problem/1912

풀이

• i번째 이전까지 연속된 부분 숫자들의 합을 계산하여, 최댓값을 그때그때 기록합니다.
  • i번째 이전까지 연속된 부분 숫자들의 합이, 그냥 i번째 숫자보다 작은 경우, 이전의 기록들은 무의미해집니다.
  • 해당 경우엔, 다시 i번째 숫자부터 연속된 부분 숫자들의 합을 구하면 됩니다.
• 예제 입력을 사용해, 시뮬레이션을 진행하면 이해가 쉽습니다.
  • [2, 1, -4, 3, 4, -4, 6, 5, -5, 1] 이 주어진 경우
  • [2, 3, -1, 3, 7, 3, 9, 14, 9, 10] 이 됩니다.

코드

import sys

# 정수 n
n = int(sys.stdin.readline())

# n개의 정수로 이루어진 수열
arr = list(map(int, sys.stdin.readline().rstrip().split(" ")))

# 연속된 부분 숫자들의 합 (첫 번째 요소는 수열의 첫 번째 숫자로 초기화)
sum = [arr[0]]

for i in range(1, n):

    # i번째 이전까지 연속된 부분 숫자들의 합보다 i번째 숫자가 큰 경우,
    # 다시 i번째 숫자부터 연속된 부분 숫자들의 합을 구하면 됩니다.
    sum.append(max(sum[i-1] + arr[i], arr[i]))

# 연속된 부분 숫자들의 합 중 최댓값 출력
print(max(sum))