前言
今天在看书中用分治法求最大连续子序列和的例子，自己想了很久。题目描述如下：
给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。输出最大连续子序列和
书中有4种方法可以来解，当时心中那个感叹啊，牛逼！其中第一种和第二种差不多，但自己对其分治方法感兴趣而已。在学习的过程中，自己想着怎么并把最大连续子序列打印出来。
第一种O(N^2)的解法
简单粗暴，以每个元素为起点来遍历。输出最大子序列。
int MaxSubSum (int a[], int n)
{
int i, j, maxSum = 0;
int left = 0; //用来记录最大子序列的第一个元素
int right = 0; //用来记录最大子序列的最后一个元素
for (i = 0; i < n; i++)
{
int thisSum = 0;
for (j = i; j < n; j++)
{
thisSum += a[j];
if (thisSum > maxSum){
left = i;
right = j;
maxSum = thisSum;
}
}
}
printfMaxSub(a,left,right); //打印输出
return maxSum;
}
定义的输出函数如下
// left 子序列的第一个元素下标; right 子序列的最后一个元素下标
void printfMaxSub(int a[],int left,int right)
{
printf("最大子序列左边的数为 %d 右边的数：%d \n",a[left],a[right]);
printf("输出最大子序列如下:");
for(int i = left; i <= right; i++)
{
printf(" %d",a[i]);
}
printf("\n");
}
第二种O(n)的解法
这个解法巧妙的是if(thisSum < 0){ //和都为负了这里不考虑 thisSum = 0; }的理解
int maxSubSequenceSum (int a[],int len)
{
int thisSum,MaxSum,j;
thisSum = MaxSum = 0;
int left = 0; //用来记录最大子序列的第一个元素
int right = 0; //用来记录最大子序列的最后一个元素
for(int i = 0; i < len; i++)
{
thisSum += a[i];
if (thisSum > MaxSum ) {
MaxSum = thisSum;
right = i;
}else if(thisSum < 0){ //和都为负了这里不考虑
thisSum = 0;
}
}
//求left 最大子序列第一个元素
int maxTemp = MaxSum;
for(int i = right; i > 0; i--)
{
maxTemp = maxTemp -a[i];
if( maxTemp > 0){
printf(" %d",a[i]);
}else if(maxTemp == 0){
printf(" %d",a[i]);
left = i;
break;
}
}
printfMaxSub(a,left,right);
return MaxSum;
}
前两种方法运行的结果如下：
int main()
{
int a[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4};
int lengTemp = sizeof(a)/sizeof(*a);
printf ("MaxSubSum is:%6d.\n", MaxSubSum(a, lengTemp));
printf("===========================\n");
printf("maxSubSequenceSum is %d\n",maxSubSequenceSum(a,lengTemp));
return 0;
}
输出.png
分治法来解
它的思想是：
1.将一个长度为n的序列，一分为二变为两个长度为n/2的子序列，继续将子序列们一分为二，直到每个子序列只含有1个整数。
2.此时问题已经足够小，“最大子序列和”有以下三种情况：左边序列的最大子序列和、右边序列的最大子序列和和处在中间位置上的最大子序列和，我们通过比较，得到三者中的最大值。
3.再将这些“小问题”合并，使用同样的比较方法逐步向上合并这些“左右序列”，直到得到整个序列的最大子序列和，解决问题。`
如下
int getMaxNum(int a,int b,int c){
if (a > b&&a > c){
return a;
}
if (b > a&&b > c){
return b;
}
return c;
}
int maxSubDivide(int data[], int left, int right)
{
if (right - left == 1){
//如果当前序列只有一个元素
return data[left];
}
int center = (left + right) / 2;//计算当前序列的分裂点
int maxLeftSum = maxSubDivide(data,left,center);
int maxRightSum = maxSubDivide(data,center,right);
//计算左边界最大子序列和
int leftBonderSum = 0;
int maxLeftBonderSum = data[center-1];
for (int i = center - 1; i >= left; i--){
leftBonderSum += data[I];
if (maxLeftBonderSum < leftBonderSum){
maxLeftBonderSum = leftBonderSum;
}
}
//计算右边界最大子序列和
int rightBonderSum = 0;
int maxRightBonderSum = data[center];
for (int i = center; i < right; i++){
rightBonderSum += data[I];
if (maxRightBonderSum < rightBonderSum){
maxRightBonderSum = rightBonderSum;
}
}
//返回当前序列最大子序列和
return getMaxNum(maxLeftBonderSum + maxRightBonderSum, maxLeftSum, maxRightSum);
}
前2个方法没考虑 全为负数的情况，后面分治法考虑了。细节int maxLeftBonderSum = data[center-1]; int maxRightBonderSum = data[center];这里给的最大值不是0
整体运行如下：
用分治法不知道输出最大连续子序列。
int main()
{
int a[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4};
int lengTemp = sizeof(a)/sizeof(*a);
printf ("MaxSubSum is:%6d.\n", MaxSubSum(a, lengTemp));
printf("===========================\n");
printf("maxSubSequenceSum is %d\n",maxSubSequenceSum(a,lengTemp));
printf("分治法 %d\n",maxSubDivide(a, 0, 9));
printf("===========================\n");
int b[]= {-2,-1,-4,-5,-1,-1,-7};
printf("xxx %d\n",MaxSubNum(b,0,7));
printf("分治法 %d\n",maxSubDivide(b, 0, 7));
return 0;
}
屏幕快照 2019-04-03 下午5.24.31.png
网友评论