백준 1912번: 연속합 python

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

문제 이해

nums[i] 혼자서 새로 시작할지 이전 dp[i-1] + nums[i]로 이어갈지
그중 더 큰 값을 선택해서 dp[i]에 저장 하는 방식으로 풀면 될 것 같다.

코드 및 풀이

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))

max_sum = nums[0]  # 전체 최대값
current_sum = nums[0]  # 현재까지의 최대 연속합

for i in range(1, n):
    current_sum = max(nums[i], current_sum + nums[i])
    max_sum = max(max_sum, current_sum)

print(max_sum)