数组为: 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());
分享到:
相关推荐
分治算法求n个数的数组中找出第二个最大元素
1. 设计程序利用分治策略求n个数的最大值和最小值。 2. 利用分治策略,在n个不同元素中找出第k个最小元素。
给定一个有n(n≥1)个整数的序列,要求求出其中最大连续子序列的和。 例如: 序列(-2,11,-4,13,-5,-2)的最大子序列和为20序列; (-6,2,4,-7,5,3,2,-1,6,-9,10,-2)的最大子序列和为16。 3.用...
求最大字段的三种方法——_动态规划_蛮力_分治算法
C++求最大子序列的和 问题:求一个数组 / 序列的满足条件的子数组 / 子序列。 条件: 1. 子数组必须是连续的。 2. 求和即可,不需要返回子数组是哪段。 3. 数组元素为整数。
最大子段和问题描述:给定由n个整数(可能为负整数)组成的序列a1, a2,…, an, 求该序列形如的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义,所求的最优值为: 例如, 当(a1,a2, a3, a4...
序列{B,C,B,A}也是X和Y的一个公共子序列,它的长度为4,而且它是X和Y的一个最长公共子序列,因为X和Y没有长度大于4的公共子序列。 最长公共子序列问题就是给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn},找出X和...
一个整数序列,求最大子序列的和,C++,The max sub sum of an array.
一般地,给定一个序列X=,x2,…,xm>,则另一个序列Z=,z2,…,zk>是X的子序列,是指存在一个严格递增的下标序列〈i1,i2,…,ik〉使得对于所有j=1,2,…,k使Z中第j个元素zj与X中第ij个元素相同。 给定2个序列X和Y,当另...
文件给出了四种方式求解子序列的最大和,并给出了具体的代码实现。对于深入探讨算法和程序性能非常有帮助。
C#,最大公共子序列(LCS,Longest Common Subsequences)的算法与源代码 最长的常见子序列问题是寻找两个给定字符串中存在的最长序列。 最大公共子序列算法,常用于犯罪鉴定、亲子鉴定等等的 DNA 比对。 1.1 子...
最近对问题 最大子段和(分治法) 最长公共子序列问题 最大子段和(动态规划)
采用动态规划法与回溯法实现了lcs算法,并显示各算法运行时间,便于对不同的输入数据测试这两个算法的优劣。
这个算法可以应用到文字录入测试的应用中,测试文字录入内容,常用的处理方法是关键字检测发,通过检测word文件中的关键字,可以测出考生操作的大概结果,但是很不准确,利用最长公共子序列算法进行文字录入测试,...
分治算法实验(用分治法查找数组元素的最大值和最小值).doc
“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 },其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序,计算给定整数序列的最大子列和。
我们都知道对象是暂时保存在内存中的,不能用U盘考走了,有时为了使用介质转移对象,并且把对象的状态保持下来,就需要把对象保存下来,这个过程就叫做序列化,通俗点,就是把人的魂(对象)收伏成一个石子(可传输...
实现了求最长公共子序列的算法,内容简单易懂,代码也很短
最大连续子序列
13,15,17,19),其中位数是15,若b=(2,4,6,8,20),其中位数为6。两个等 长有序序列的中位数是含它们所有元素的有序序列的中位数,例如a、b两 个有序序列的中位数为11。设计一个算法求给定的两个有序序列的中 位数。