사용자 도구

사이트 도구


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을 대신 리턴하면 된다.

관련 문제

토론

댓글을 입력하세요:
H W Q V L
 
ps/최대_부분합.txt · 마지막으로 수정됨: 2022/05/29 16:18 저자 teferi