借助 求 一个序列中最大和子序列 学习 分治算法 code in C#

数组为： 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());