使用分治法解最大连续子序列和问题

俺是菜鸟了解一下，这是我在算法学习中的一些想法，如果有写的不好的还请谅解，欢迎学习交流_(:3」∠)_

问题：有长度为n的整数序列，求一段连续的子序列，要求该子序列的和为最大，并求出最大值。

用分治法解决最大子序列和问题使用的是递归，它的思想是：

1.将一个长度为n的序列，一分为二变为两个长度为n/2的子序列，继续将子序列们一分为二，直到每个子序列只含有1个整数。

2.此时问题已经足够小，“最大子序列和”有以下三种情况：左边序列的最大子序列和、右边序列的最大子序列和和处在中间位置上的最大子序列和，我们通过比较，得到三者中的最大值。

3.再将这些“小问题”合并，使用同样的比较方法逐步向上合并这些“左右序列”，直到得到整个序列的最大子序列和，解决问题。

在这个问题中，分为两种情况：1.序列含有正整数；2.序列不含正整数。我的想法是可以对这两种情况分别使用对应的函数。

第一种情况，序列含有正整数，算法的时间复杂度为O(nlog(n))：

int MaxSubseqSum(int a[],int left,int right){int maxLeftSum,maxRightSum,maxMidSum;int maxLeftBorderSum,LeftBorderSum;int maxRightBorderSum,RightBorderSum;int mid;int i;if(left==right)//递归出口，子序列只有一个元素时return a[left];mid=(left+right)/2;//求中间位置maxLeftSum=MaxSubseqSum(a,left,mid);//求左边序列的最大子序列和maxRightSum=MaxSubseqSum(a,mid+1,right);//求右边序列的最大子序列和maxLeftBorderSum=0;LeftBorderSum=0;for(i=mid;i>=left;i--)//从中间位置向左找靠边界的最大子序列{LeftBorderSum+=a[i];if(LeftBorderSum>maxLeftBorderSum)maxLeftBorderSum=LeftBorderSum;}maxRightBorderSum=0;RightBorderSum=0;for(i=mid+1;i<=right;i++)//从中间位置向右找靠边界的最大子序列{RightBorderSum+=a[i];if(RightBorderSum>maxRightBorderSum)maxRightBorderSum=RightBorderSum;}maxMidSum=maxLeftBorderSum+maxRightBorderSum;//得到处在中间位置上的最大子序列和return max3(maxLeftSum,maxRightSum,maxMidSum);}

第二种情况，序列不含正整数，可以改为使用分治法取序列中最大的数，算法的时间复杂度为O(log(n))：

int MaxNum(int a[],int left,int right){int maxLeft,maxRight;int mid;if(left==right)return a[left];mid=(left+right)/2;maxLeft=MaxNum(a,left,mid);maxRight=MaxNum(a,mid+1,right);return maxLeft>maxRight?maxLeft:maxRight;}

完整运行代码：

#include<stdio.h>#define MAXSIZE 100int max3(int a,int b,int c){if(a>b) return a>c?a:c;else return b>c?b:c;}int MaxSubseqSum(int a[],int left,int right){int maxLeftSum,maxRightSum,maxMidSum;int maxLeftBorderSum,LeftBorderSum;int maxRightBorderSum,RightBorderSum;int mid;int i;if(left==right)//递归出口，子序列只有一个元素时return a[left];mid=(left+right)/2;//求中间位置maxLeftSum=MaxSubseqSum(a,left,mid);//求左边序列的最大子序列和maxRightSum=MaxSubseqSum(a,mid+1,right);//求右边序列的最大子序列和maxLeftBorderSum=0;LeftBorderSum=0;for(i=mid;i>=left;i--)//从中间位置向左找靠边界的最大子序列{LeftBorderSum+=a[i];if(LeftBorderSum>maxLeftBorderSum)maxLeftBorderSum=LeftBorderSum;}maxRightBorderSum=0;RightBorderSum=0;for(i=mid+1;i<=right;i++)//从中间位置向右找靠边界的最大子序列{RightBorderSum+=a[i];if(RightBorderSum>maxRightBorderSum)maxRightBorderSum=RightBorderSum;}maxMidSum=maxLeftBorderSum+maxRightBorderSum;//得到处在中间位置上的最大子序列和return max3(maxLeftSum,maxRightSum,maxMidSum);}int MaxNum(int a[],int left,int right){int maxLeft,maxRight;int mid;if(left==right)return a[left];mid=(left+right)/2;maxLeft=MaxNum(a,left,mid);maxRight=MaxNum(a,mid+1,right);return maxLeft>maxRight?maxLeft:maxRight;}void main(){int a[MAXSIZE];int count=0;int i,n;printf("序列长度:");scanf("%d",&n);printf("输入整数序列:");for(i=0;i<n;i++){scanf("%d",&a[i]);if(a[i]<=0)count++;}if(count==n)//判断是否含有正整数printf("最大子序列和:%d\n",MaxNum(a,0,n-1));elseprintf("最大子序列和:%d\n",MaxSubseqSum(a,0,n-1));}

如果觉得《使用分治法解最大连续子序列和问题》对你有帮助，请点赞、收藏，并留下你的观点哦！