문제: https://www.acmicpc.net/problem/1912

설명

이 문제는 배열의 범위를 어떻게 설정하느냐에 따라 답이 달라진다.

그리고 배열의 범위는 배열의 연속합을 구하는 시작 위치로 구할 수 있다.

일단 dp 배열을 생성한다.
이 배열이 의미하는 바는 배열의 인덱스를 i라고 할 때, 0부터 i 범위의 배열에서 연속합의 최댓값을 말한다.

예를들어, dp[2]를 구한다면 인덱스 2이전의 배열에서 dp의 최대값에 arr[2]를 더한 것과 시작점이 2이고 크기가 1인 배열을 비교하면 된다.
아래의 그림을 이를 설명한다.

코드

from sys import stdin as s
import sys

s = open("input.txt", "rt")

n = int(s.readline())

arr = list(map(int, s.readline().split()))
dp = arr

def findMaxSum():
    for i in range(1, len(dp)):
        dp[i] = max(dp[i-1] + arr[i], dp[i])
findMaxSum()

# 각 구간의 연속합의 최댓값을 구했으니 가장 큰 값을 출력하면 된다.
print(max(dp))