백준: 1912 연속합

문제

1912번: 연속합

 

문제 풀이

 다음과 같은 조건을 통해, 한번의 계산으로 연속합 중의 최대 값을 찾을 수 있다. 현재 수열 값이 앞의 값과 더한 것 보다 값이 크면 그대로 유지하고 아닐 경우, 앞의 합산 값으로 갱신한다. 말로는 잘 이해가 안되지만 문제 예시에서 최대 값을 구하는 과정을 보면 쉽게 이해할 수 있다.

 

Origin	10	-4	3	1	5	6	-35	12	21
Round 1	10	6
Round 2	10	6	9
Round 3	10	6	9	10
Round 4	10	6	9	10	15
Round 5	10	6	9	10	15	21
Round 6	10	6	9	10	15	21	-14
Round 7	10	6	9	10	15	21	-14	12
Round 8	10	6	9	10	15	21	-14	12	33

• 누적된 값이 현재 수열 값(인덱스) 보다 크다면 누적된 새로운 값으로 갱신한다. (파란색)
• 누적된 값이 현재 수열 값 보다 작다면 현재 값을 유지한다 (빨간색)
• 이와 같은 방식을 통해 더 이상 값이 증가하지 않는 부분에 대한 부분합과 그 이후의 부분합을 계산할 수 있다.

 

코드

from sys import stdin

if __name__ == '__main__':
    n = int(stdin.readline())
    nums = list(map(int, stdin.readline().split()))

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

    print(max(nums))