ps:최대_부분합
최대 부분합 (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. 이쪽은 원형으로 이루어진 배열에서 최대부분합을 찾는 변형
ps/최대_부분합.txt · 마지막으로 수정됨: 2023/07/27 14:09 저자 teferi
토론