[알고리즘] 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)를 포함하여 양쪽에 걸쳐 있을 경우
다시 코드를 살펴보자.
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 이다.