首页 > 代码库 > 第四章 分治策略——最大子数组问题
第四章 分治策略——最大子数组问题
最大子数组问题
方法一：暴力求解方法
我们可以很容易地设计出一个暴力方法来求解本问题：简单地尝试没对可能的子数组，共有O(n2)种
#include<iostream>using namespace std;#define INT_MIN 0x80000000int main(){ int arr[10]={9,8,-3,-5,7,-39,79,-37,8,9}; int i,j; int sum=0,maxsum=INT_MIN; int imax; for(i=0;i<10;i++) { sum=0; for(j=i;j<10;j++) { sum+=arr[j]; if(maxsum<sum) { maxsum=sum; imax=j; } } } cout<<"maxsum: "<<maxsum<<" imax:"<<imax<<endl;}方法二：使用分治策略的求解方法（O(nlgn)）
我们来思考如何用分治技术来求解最大子数组问题。假定我们要寻找子数组A[low,high]的最大子数组。使用分治技术意味着我们要将子数组划分为两个规模尽量相等的子数组。也就是说，找到子数组的中央位置，比如mid，然后考虑求解两个子数组A[low,mid]和A[mid+1,high]。则A[low,high]的任何连续子数组A[i..j]所处的位置必定是以下3种情况之一：
- 完全位于子数组A[low..mid]中，因此low<=i<=j<=mid
- 完全位于子数组A[mid+1..high]中，因此mid<i<=j<=high;
- 跨越了中点，因此low<=i<=mid<j<=high;
因此，A[low..high]的一个最大子数组所处的位置必然是这三种情况之一。实际上，A[low,high]的一个最大子数组必然是完全位于A[low..mid]中，完全位于A[mid+1..high]中或者跨越中点的所有子数组中和最大者。我们可以递归地求解A[low,mid]和A[mid+1,high]的最大子数组，因为这两个子问题仍然是最大子数组的问题，只是规模更小。因此，剩下的全部工作就是寻找跨越中点的最大子数组，然后在三种情况中选取和最大者。
算法如下：
#include<iostream>#include<tuple>using namespace std;#define INT_MIN 0x80000000tuple<int,int,int> FindMaxCrossingSubarry(int arr[],int low,int mid,int high){ int leftsum=INT_MIN,rightsum=INT_MIN; int sum=0; int maxleft=low,maxright=mid+1; int i; for(i=mid;i!=low;i--) { sum+=arr[i]; if(leftsum<sum) { leftsum=sum; maxleft=i; } } sum=0; for(i=mid+1;i!=high;i++) { sum+=arr[i]; if(rightsum<sum) { rightsum=sum; maxright=i; } } cout<<"maxleft: "<<maxleft<<" maxright: "<<maxright<<" leftsum+rightsum: "<<leftsum+rightsum<<endl; return tuple<int,int,int>(maxleft,maxright,leftsum+rightsum);}tuple<int,int,int> FindMaximumSubarry(int arr[],int low,int high){ if(low==high) return tuple<int,int,int>(low,high,arr[low]); else { int mid=(low+high)/2; tuple<int,int,int> left=FindMaximumSubarry(arr,low,mid); tuple<int,int,int> right=FindMaximumSubarry(arr,mid+1,high); tuple<int,int,int> middle=FindMaxCrossingSubarry(arr,low,mid,high); if(get<2>(left)>=get<2>(right)&&get<2>(left)>=get<2>(middle)) return left; else if(get<2>(right)>=get<2>(left)&&get<2>(right)>=get<2>(middle)) return right; else return middle; }}int main(){ int arr[10]={9,8,-3,-5,7,-39,79,-37,8,9}; tuple<int,int,int> result=FindMaximumSubarry(arr,0,9); cout<<get<0>(result)<<" "<<get<1>(result)<<" "<<get<2>(result)<<endl;}方法三：使用动态规划的算法（O(n)）
#include<iostream>using namespace std;int MaxArraySum(int arr[],int n){ int sum,maxSum,maxi; int i; maxSum=0; maxi=0; sum=0; for(i=0;i<n;i++) { sum+=arr[i]; if(sum<0) { sum=0; continue; } if(maxSum<sum) { maxSum=sum; maxi=i; } } cout<<"max sum: "<<maxSum<<" index: "<<maxi<<endl; return maxSum;}int main(){ int arr[10]={9,8,-3,-5,7,-39,79,-37,8,9}; cout<<MaxArraySum(arr,10);}
第四章 分治策略——最大子数组问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。