[알고리즘] Maximum-subarray 구하기 (Divide-and-conquer 활용)

1. Maximum-subarray 코드

 

def FindMaximumSubarray(A, low, high):
    if high < low:
        return 0, 0, 0

    if high == low:
        return low, high, A[low]

    else:
        mid = (low + high) // 2
        (left_low, left_high, left_sum) = FindMaximumSubarray(A, low, mid - 1)
        (right_low, right_high, right_sum) = FindMaximumSubarray(A, mid + 1, high)
        (cross_low, cross_high, cross_sum) = FindMaxCrossingSubarray(A, low, mid, high)

        if left_sum >= right_sum and left_sum >= cross_sum:
            return left_low, left_high, left_sum
        elif right_sum >= left_sum and right_sum >= cross_sum:
            return right_low, right_high, right_sum
        else:
            return cross_low, cross_high, cross_sum

def FindMaxCrossingSubarray(A, low, mid, high):
    left_sum = 0
    right_sum = 0
    max_left = 0
    max_right = 0
    flag_left = True
    flag_right = True

    sum = 0
    for i in range(mid - 1, low - 1, -1):
        sum = sum + A[i]
        if sum > left_sum:
            left_sum = sum
            max_left = i
            flag_left = False

    sum = 0
    for j in range(mid + 1, high + 1, 1):
        sum = sum + A[j]
        if sum > right_sum:
            right_sum = sum
            max_right = j
            flag_right = False

    if flag_left:
        max_left = mid
    if flag_right:
        max_right = mid

    return max_left, max_right, left_sum + right_sum + A[mid]


A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(FindMaximumSubarray(A, 0, 8))     # param : (Array, start, end)

 

위의 코드는 배열의 Maximum-subarray을 구하는 python 코드다.

 

 

 

2. 기본 알고리즘

 

Maximum-subarray는 전체 배열이 있을 경우 각 원소들의 합이 최대가 되는 연속적인 부분 배열을 찾는 것을 의미한다.

예를 들어 [1, -5, 3, 6, -2] 라는 배열이 있을 경우, [3, 6] 이라는 연속적인 부분배열이 각 원소들의 합이 9로 가장 크므로 해당 배열의 Maximum-subarray는 [3, 6]이 된다.

 

Maximum-subarray은 기본적으로 Divide-and-Conquer 알고리즘을 이용한다.

 

Maximum-subarray을 풀때는 아래와 같이 3가지 경우로 나누어 문제를 풀어나간다. 

 

  Case 1) Maximum-subarray 배열이 가운데 원소(mid)를 기준으로 왼쪽에 있을 경우

  Case 2) Maximum-subarray 배열이 가운데 원소(mid)를 기준으로 오른쪽에 있을 경우

  Case 3) Maximum-subarray 배열이 가운데 원소(mid)를 포함하여 양쪽에 걸쳐 있을 경우

 

Maximum-subarray의 3가지 경우

 

다시 코드를 살펴보자.

 

def FindMaxCrossingSubarray(A, low, mid, high):
    left_sum = 0
    right_sum = 0
    max_left = 0
    max_right = 0
    flag_left = True
    flag_right = True

    sum = 0
    for i in range(mid - 1, low - 1, -1):
        sum = sum + A[i]
        if sum > left_sum:
            left_sum = sum
            max_left = i
            flag_left = False

    sum = 0
    for j in range(mid + 1, high + 1, 1):
        sum = sum + A[j]
        if sum > right_sum:
            right_sum = sum
            max_right = j
            flag_right = False

    if flag_left:
        max_left = mid
    if flag_right:
        max_right = mid

    return max_left, max_right, left_sum + right_sum + A[mid]

 

FindMaxCrossingSubarray 함수는 parameter로 어떤 배열이 들어왔을 때, mid값을 정하고 case 3) 에 해당하는 최댓값을 찾는 함수이다. (mid 값 기준 Crossing 하는 경우)

 

우선 첫번째 for 문에서 mid 기준 왼쪽의 최댓값을 구하고 두번째 for 문에서 mid 기준 오른쪽의 최댓값을 구한다.

위의 두 값에 mid에 해당하는 값을 더해 mid를 포함하여 양쪽에 있을 경우의 최댓값을 구한다.

 

 

def FindMaximumSubarray(A, low, high):
    if high < low:
        return 0, 0, 0

    if high == low:
        return low, high, A[low]

    else:
        mid = (low + high) // 2
        (left_low, left_high, left_sum) = FindMaximumSubarray(A, low, mid - 1)
        (right_low, right_high, right_sum) = FindMaximumSubarray(A, mid + 1, high)
        (cross_low, cross_high, cross_sum) = FindMaxCrossingSubarray(A, low, mid, high)

        if left_sum >= right_sum and left_sum >= cross_sum:
            return left_low, left_high, left_sum
        elif right_sum >= left_sum and right_sum >= cross_sum:
            return right_low, right_high, right_sum
        else:
            return cross_low, cross_high, cross_sum

 

FindMaximumSubarray 함수는 특정 배열이 입력되었을 경우, 위의 Case 1) 2) 3) 중 결과값이 가장 큰 Maximum-Subarray의 시작 index, 끝 index, 총합을 리턴하는 함수이다.

 

Case1) 2)의 경우는 FindMaximumSubarray 함수에 subarray를 parameter로 하여, 재귀적으로 호출함으로써 계산하며, Case 3)의 경우는 위에서 작성한 FindMaxCrossingSubarray 함수를 호출하여 계산한다.

 

 

 

3. 시간복잡도

 

Maximum-subarray 문제를 Divide-and-conquer 방식으로 풀 경우, 시간 복잡도는 n log n 이다.