연습문제 4.1-5 최대 부분배열 찾기 선형시간 알고리즘

앞에서 n^2 과 nlgn의 수행시간을 갖는 최대 부분합 탐색 알고리즘을 구현해 봤는데 이번에는 n 시간인 알고리즘을 구현해봤다. 이번에는 재귀로 분할을 하는 것도 아니고 모든 분할합들을 비교하지도 않는다. 작은 문제에서 시작해서 문제를 확장시켜 나간다. 책에 나온 힌트를 토대로 내가 구현해 본 코드는 아래와 같다.

def maximum_sub(a):
    for i,value in enumerate(a):
        if(i==0):
            left_idx = 0
            right_idx = 0
            maximum_sum = value
            tail_maximum_sum = value
            tail_left_idx = 0
        else:
            if tail_maximum_sum>0:
                tail_maximum_sum += value
            else:
                tail_maximum_sum = value
                tail_left_idx = i
            if tail_maximum_sum >= maximum_sum :
                maximum_sum = tail_maximum_sum
                left_idx = tail_left_idx
                right_idx = i
    return left_idx, right_idx, maximum_sum

원소가 1개인 배열에서 최대 부분합은 당연히 left_idx=0, right_idx=0에 합은 A[0]이다. 여기서 오른쪽에 리스트를 하나 더 추가해주자.

전 단계의 마지막 인덱스를 포함하는 최대합의 값이 음수라면 마지막 원소 하나만을 갖는 부분합이 최대의 부분합이 된다. 그렇지 않은경우 새로운 원소가 무엇이든 간에 해당 원소를 포함해야 마지막 원소를 포함하는 부분합이라는 조건을 만족하므로 tail_maximum_sum이 갱신된다.

원소가 추가 됨으로써 새로 추가된 원소를 포함하는 최대합과 포함하지 않는 최대합 두가지의 경우가 나올 수 있는데, 이 두가지를 비교해서 더 큰쪽의 인덱스를 기록한다. tail_maximum_sum역시 그대로 기억을 해놔야 다음 단계의 tail_maximum_sum을 빠르게 구해줄 수 있다.

이렇게 for loop을 한번만 돌면서 마지막 원소까지 추가를 해주면 최대 합을 구할 수 있다. loop invariant로 증명 해도 쉽게 증명 될 것 같음.