lesson 9 개요

$n$개의 수 $a_0, a_1, ..., a_{n-1}$에 대해 가장 큰 부분합을 구하는 문제에 대해 생각해보자.

위 그림의 예시에서, 가장 큰 부분합은 색칠된 부분이고 그 합은 10이다.

알고리즘 문제를 좀 풀어봤다면, 이 문제는 dp로 해결할 수 있고 그 시간복잡도는 $O(n)$이다.

def max_slice(L):
    # max_end: x가 부분합의 마지막 원소일 때, 그 최대 부분합
    # max_sum: 지금까지 탐색한 부분합중 최댓값
    max_end, max_sum = 0
    
    for x in L:
    	max_end = max(0, max_end + x)
        max_sum = max(max_sum, max_end)
    return max_sum