数组为: int[] args = { -2, 11, -4, 13, -5, 2, -5, -3, 12, -9 };
最大和为:21
分治(devide-and-conquer):
其想法是把问题分成两个大致相等的子问题,然后递归地对他们求解,这是“分”的部分。“治”阶段将两个子问题的解修补到一起并可能再做些少量的附加工作,最后得到整个问题的解。
对于上面的测试数据被分成两组 {-2, 11, -4, 13,-5} ;{ 2, -5, -3, 12, -9}。最终结果存在种可能:在left数组中;在right数组中;找到包含
left最后一个元素(在例子中是
-5
)在
left
的最大子序列(例子中是
11, -4, 13,-5)和包含
right起始元素(2
)在
Second
的最大子序列(
2, -5, -3, 12)然后相加的结果。
下面我把我简要写的C#测试代码粘贴如下:
/// <summary>
/// 分治 算法
/// </summary>
/// <param name="a">A.</param>
/// <param name="left">The left.</param>
/// <param name="right">The right.</param>
/// <returns></returns>
int getMaxSumUsingDivideConquer(int[] a, int left, int right)
{
if (left == right)
{
if (args[left] > 0)
{
return args[left];
}
else
{
return 0;
}
}
int center = (left + right) / 2;
int maxLeftSum = getMaxSumUsingDivideConquer(a, left, center);
int maxRightSum = getMaxSumUsingDivideConquer(a, center + 1, right);
int maxLeftBorderSum = 0, leftBorderSum = 0;
for (int i = center; i >= left; i--)
{
leftBorderSum += a[i];
if (leftBorderSum > maxLeftBorderSum)
{
maxLeftBorderSum = leftBorderSum;
}
}
int maxRightBorderSum = 0, RightBorderSum = 0;
for (int i = center + 1; i <= right; i++)
{
RightBorderSum += a[i];
if (RightBorderSum > maxRightBorderSum)
{
maxRightBorderSum = RightBorderSum;
}
}
return GetMaxValueFromTreeNumber(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum); // 判断三个数最大值的函数
}
/// <summary>
/// Gets the max value from tree number.
/// </summary>
/// <param name="maxLeftSum">The max left sum.</param>
/// <param name="maxRightSum">The max right sum.</param>
/// <param name="third">The third.</param>
/// <returns></returns>
private int GetMaxValueFromTreeNumber(int maxLeftSum, int maxRightSum, int third)
{
int max = 0;
if (max < maxLeftSum)
{
max = maxLeftSum;
}
if (max < maxRightSum)
{
max = maxRightSum;
}
if (max < third)
{
max = third;
}
return max;
}
具体调用方法如下:
int total = getMaxSumUsingDivideConquer(args, 0, args.Length - 1);
MessageBox.Show("the value of maxSum is:" + total.ToString());