목차

최대 부분합 (Maximum subarray problem)
- 코드 (Kadane algorithm)
- 관련 문제
토론

최대 부분합 (Maximum subarray problem)

주어진 배열의 부분배열중에서 합이 최대가 되는 것을 찾는 문제. Maximum_subarray_problem를 참고
가장 무식한 방법은 O(n^2)개의 모든 구간에 대해서 일일히 합을 전부 계산해보는것. O(n^3)이 된다
- Prefix sum을 이용해서 구간합을 O(1)에 구한다면 O(n^2)으로 줄일수 있다
분할정복을 이용해서 O(nlogn)에 계산이 가능하다.
- 이 방식을 세그먼트 트리에 접목시켜서, 배열의 범위를 주면 그 안에서의 최대 부분합을 구하는 작업을 O(logn)에 처리하는 테크닉이 존재한다. 일명 금광세그라고 불리우는 기법이다.
다이나믹 프로그래밍을 이용해서 O(n)에 계산이 가능하다.
- 이것은 Kadane algorithm 이라고 불린다. 빠를뿐 아니라 코드도 심플해서 굳이 다른 방법을 쓸 필요가 없다.

코드 (Kadane algorithm)

def maximum_subarray(nums):
    max_sum, cur_sum = -INF, 0
    for num in nums:
        cur_sum = max(num, cur_sum + num)
        max_sum = max(max_sum, cur_sum)
    return max_sum

만약 문제 조건에서 빈 부분배열을 선택하는 것이 가능할 경우에는, 구한 결과가 0보다 작은지 체크해서 작으면 0을 대신 리턴하면 된다.

관련 문제

연속합 : n<100,000
Maximum Subarray : n<1000
Equator : n<1,000,000. 이쪽은 원형으로 이루어진 배열에서 최대부분합을 찾는 변형