俺是菜鸟了解一下,这是我在算法学习中的一些想法,如果有写的不好的还请谅解,欢迎学习交流_(: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));}
如果觉得《使用分治法解最大连续子序列和问题》对你有帮助,请点赞、收藏,并留下你的观点哦!