====== 최대 부분합 (Maximum subarray problem) ======

  * 주어진 배열의 부분배열중에서 합이 최대가 되는 것을 찾는 문제. [[wp>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) =====

  * <dkpr py>
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
</dkpr>
  * 만약 문제 조건에서 빈 부분배열을 선택하는 것이 가능할 경우에는, 구한 결과가 0보다 작은지 체크해서 작으면 0을 대신 리턴하면 된다.

===== 관련 문제 =====
  * [[ps:problems:boj:1912]] : n<100,000
  * [[ps:problems:boj:10211]] : n<1000
  * [[ps:problems:boj:10274]] : n<1,000,000. 이쪽은 원형으로 이루어진 배열에서 최대부분합을 찾는 변형