백준 1912. 연속합

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

1912번: 연속합

이중 반복문을 쓰자니 시간 초과가, 그렇다고 2000개 크기의 배열을 생성하자니 메모리 초과가 떠서 고민했던 문제.

문제를 풀다보니 DP는 약간 수열틱(?) 하구나 라는 감을 잡게 되었다.

 

예제 기준으로 최대 부분합 후보를 나열해보면 다음과 같다.

최대 부분합 후보를 계속 구하다가, 후보가 특정 한 값보다 작아지면 최대 부분합 후보 탈락이므로 업데이트를 해주면 된다.

위 경우에는 -14 +12 = -2 < 12 이므로 그동안의 부분합이 최대가 될 수 없고, 따라서 최대 부분합 후보를 12로 바꿔준다.

 

n = int(input())

nums = list(map(int, input().split()))
arr = [0] * n
arr[0] = nums[0]
for i in range(1, n):
	arr[i] = max(nums[i], nums[i] + arr[i - 1]) #새로 등장한 수와 최대 부분합 후보 비교

print(max(arr))