分治求解最大子数组
分治求解步骤
- 分:将数组分成左右两部分
- 治:递归地求解左半部分和右半部分的最大子数组
- 合:计算跨越中点的最大子数组,并取三者中的最大值
具体实现
-
分:
将数组A分成两部分
左半部分:从low到mid
右半部分:从mid+1 到high
mid为low+high的中点
-
治
递归求解左半部分和右半部分的最大子数组
-
合
计算跨越中点的最大子数组。这需要从中点县向左和向右分别扩展,找到包括中点的最大子数组
#include <limits.h>
#include <stdio.h>
int findMaxCrossingSubarrary(int A[], int low, int mid, int high, int *maxLeft, int * maxRight)
{
int leftSum = INT_MIN;
int sum = 0;
int i;
for(i = mid; i >= low; i--)
{
sum += A[i];
if(sum > leftSum)
{
leftSum = sun;
*maxLeft = i;
}
}
}
int findMaxSubarrary(int A[], int low, int high, int *maxLeft, int *maxRight)
{
if(low == high)
{
*maxLeft = low;
*maxRight = high;
return A[low];
}
else
{
int mid = (low + high) / 2;
int leftLow, leftHigh, rightLow, rightHigh, crossLow, crossHigh;
int leftSum = findMaxSubarrary(A, low, mid, &leftLow, &leftHigh);
int rightSum = findMaxSubarrary(A, mid + 1, high, &rightLow, &rightHigh);
int crossSum = findMaxCrossingSubarrary(A, low, mid, high, &crossLow, &crossHigh);
if(leftSum >= rightSum && leftSum >= crossSum)
{
*maxLeft = leftLow;
*maxRight = leftHigh;
return leftSum;
}else if(rightSum >= leftSum && rightSum >= crossSum)
{
*maxLeft = rightLow;
*maxRight = rightHigh;
return rightSum;
}else
{
*maxLeft = crossLow;
*maxRight = crossHigh;
return crossSum;
}
}
}
int main()
{
int A[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
int n = sizeof(A) / sizeof(A[0]);
int low = 0;
int high = n - 1;
int maxLeft, maxRight;
int maxSum = findMaxSubarrary(A, low, high, &maxLeft, &maxRight);
printf("maximum subarry: [%d, %d] with sum %d\n", maxLeft, maxRight, maxSum);
return 0;
}
分:在 findMaxSubarray
函数中,通过计算 mid
将数组分成左右两部分。
治:递归调用 findMaxSubarray
函数分别求解左半部分和右半部分的最大子数组。
合:调用 findMaxCrossingSubarray
函数计算跨越中点的最大子数组。将左右两部分和跨越中点的最大子数组中的最大值作为结果返回