최대 하위 배열 문제 및 kadane&#s 알고리즘

최대 하위 배열 문제와 그 역사

1970년대 후반, 스웨덴 수학자 Ulf Grenander는 문제에 대해 논의했습니다. 어떻게 하면 무차별 대입보다 더 효율적으로 이미지 데이터의 2D 배열을 분석할 수 있습니까? 그 당시 컴퓨터는 느리고 RAM에 비해 사진의 크기가 컸습니다. 상황을 악화시키기 위해 최악의 시나리오에서 무차별 대입은 O(n^6) 시간(육성 시간 복잡성)이 걸렸습니다.

먼저 Grenandier는 질문을 단순화했습니다. 1차원 숫자 배열이 주어지면 합이 가장 큰 인접한 하위 배열을 가장 효율적으로 찾는 방법은 무엇입니까?

무차별 대입: 3차 시간 복잡도를 사용한 순진한 접근 방식

무차별 대입 방식으로 1D 배열을 2D 배열로 분석하는 데 걸리는 시간은 절반이므로 가능한 모든 조합(입방 시간 복잡도)을 검사하려면 O(n^3)이 필요합니다.

def max_subarray_brute_force(arr):
    max_sum = arr[0] # assumes arr has a length

    # iterate over all possible subarrays
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            current_sum = 0
            # sum the elements of the subarray arr[i:j+1]
            for k in range(i, j + 1):
                current_sum += arr[k]
            # update max_sum if the current sum is greater
            max_sum = max(max_sum, current_sum)

    return max_sum

print(max_subarray_brute_force([-2, -3, 4, -1, -2, 1, 5, -3]), "== 7")

Grenander의 O(n²) 최적화: 한 단계 발전

Grenander는 이를 O(n^2) 솔루션으로 개선했습니다. 내 연구에서는 그의 코드를 찾을 수 없었지만 내 추측으로는 그는 단순히 두 지수 사이의 모든 숫자를 더하는 가장 안쪽 루프를 제거한 것 같습니다. 대신 하위 배열을 반복하는 동안 누적 합계를 유지하여 루프 수를 3개에서 2개로 줄일 수 있습니다.

def max_subarray_optimized(arr):
    max_sum = arr[0]  # assumes arr has a length

    # iterate over all possible starting points of the subarray
    for i in range(len(arr)):
        current_sum = 0
        # sum the elements of the subarray starting from arr[i]
        for j in range(i, len(arr)):
            current_sum += arr[j]
            # update max_sum if the current sum is greater
            max_sum = max(max_sum, current_sum)

    return max_sum

샤모스의 분할 정복: 문제를 O(n log n)으로 나누기

Grenander는 컴퓨터 과학자인 Michael Shamos에게 문제를 보여주었습니다. 샤모스는 하룻밤 동안 고민하다가 O(n log n) 분할 정복 방법을 떠올렸습니다.

정말 영리하네요. 아이디어는 배열을 두 부분으로 나눈 다음 각 절반에 대한 최대 하위 배열 합계와 중간점을 교차하는 하위 배열을 재귀적으로 찾는 것입니다.

def max_crossing_sum(arr, left, mid, right):
    # left of mid
    left_sum = float('-inf')
    current_sum = 0
    for i in range(mid, left - 1, -1):
        current_sum += arr[i]
        left_sum = max(left_sum, current_sum)

    # right of mid
    right_sum = float('inf')
    current_sum = 0
    for i in range(mid + 1, right + 1):
        current_sum += arr[i]
        right_sum = max(right_sum, current_sum)

    # sum of elements on the left and right of mid, which is the maximum sum that crosses the midpoint
    return left_sum + right_sum

def max_subarray_divide_and_conquer(arr, left, right):
    # base case: only one element
    if left == right:
        return arr[left]

    # find the midpoint
    mid = (left + right) // 2

    # recursively find the maximum subarray sum for the left and right halves
    left_sum = max_subarray_divide_and_conquer(arr, left, mid)
    right_sum = max_subarray_divide_and_conquer(arr, mid + 1, right)
    cross_sum = max_crossing_sum(arr, left, mid, right)

    # return the maximum of the three possible cases
    return max(left_sum, right_sum, cross_sum)

def max_subarray(arr):
    return max_subarray_divide_and_conquer(arr, 0, len(arr) - 1)


print(max_subarray([-2, -3, 4, -1, -2, 1, 5, -3]), "== 7")

먼저 배열을 두 부분(O(logn))으로 나눈 다음 최대 교차 하위 배열을 찾는 데 O(n)이 걸리기 때문에 시간 복잡도가 O(nlogn) 시간으로 줄어듭니다.

Kadane의 알고리즘: 우아한 O(n) 솔루션

Stastician Jay Kadane은 코드를 살펴본 후 Shamos의 솔루션이 솔루션의 일부로 연속성 제한을 사용하지 못했다는 것을 즉시 확인했습니다.

그가 깨달은 사실은 다음과 같습니다

-배열에 음수만 있는 경우 빈 하위 배열을 허용하지 않는다는 가정 하에 답은 항상 배열에서 가장 큰 단일 숫자가 됩니다.

-배열에 양수만 있는 경우 대답은 항상 전체 배열을 더하는 것입니다.

-양수와 음수가 모두 포함된 배열이 있는 경우 배열을 단계별로 탐색할 수 있습니다. 보고 있는 숫자가 그 이전의 모든 숫자의 합보다 큰 경우, 솔루션에는 이전 숫자가 포함될 수 없습니다. 따라서 지금까지 발생한 최대 합계를 추적하면서 현재 숫자에서 새 합계를 시작합니다.

maxSubArray(nums):
    # avoiding type errors or index out of bounds errors
    if nums is None or len(nums) == 0:
        return 0


    max_sum = nums[0]  # max sum can't be smaller than any given element
    curr_sum = 0

    # Kadane's algorithm
    for num in nums:
        curr_sum = max(num, curr_sum + num)
        max_sum = max(curr_sum, max_sum)
    return max_sum

제가 이 알고리즘을 좋아하는 이유는 다른 많은 문제에도 적용할 수 있다는 점입니다. LeetCode 문제를 해결하려면 이를 적용해 보세요.

1과 0
최대 합계 원형 하위 배열
최소 크기 하위 배열 합계
최대 오름차순 하위 배열 합계
최대 제품 하위 배열
연속 하위 배열 합계
최대 교번합 하위 배열(프리미엄)
K보다 크지 않은 직사각형의 최대 합

위 내용은 최대 하위 배열 문제 및 kadane&#s 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!