[BaekJoon] 1912번 : 연속합

1912번 : 연속합

처음 문제에 접근 할 땐 prefix_sum 을 이용하여 구간합을 구한 뒤 모든 부분 합 중 최대값을 반환했다.

역시나 시간초과가 발생 해 모든 부분 합을 구하는 방법의 시간 복잡도를 줄이도록 해봤다.

하지만 또 시간초과.. 정답은 아주 간단한 DP 였다..

정말 DP 문제가 세상에서 제일 어렵다..

이 문제에서는 연속해서 더할지 새로 시작할지를 정해 계산을 해준다.

---

def solution():
	dp = [data[0]]
	for i in range(n - 1):
		dp.append(max(dp[i] + data[i + 1], data[i + 1]))
    
	return max(dp)


if __name__ == "__main__":
	n = int(input())
	data = list(map(int, input().split()))

	print(solution())