将长度为n的序列L划分成两个子序列，即 L(1，n/2) 和 L(n/2 + 1 ，n)
会出现3种情况：
① max{ L(1，n) }=max{ L(1，n/2)}
② max{ L(1，n) }=max{ L(n/2 + 1 ，n) }
③max{ L(1，n) } = 且
求解子问题：对于划分阶段的情况①和②可以递归求解，情况③需要分别计算 s1 = max{} s2同理
则 s1+s2为情况三的最大子段和
合并：比较三种情况下的最大子段和，取三者最大的那个
#include
using namespace std;
int max(int x,int y){
return x>y?x:y;
}
int maxSum(int *nums,int left,int right){
if(left==right)return nums[left];
int mid=(left+right)/2;
int lsum,rsum;
lsum = maxSum(nums,left,mid); // 左边最大子段
rsum = maxSum(nums,mid+1,right); // 右边最大子段
//求中间最大子段
int s1=0,s2=0;
int temp=0;
for(int i=mid;i>=left;i++){ // 注意：这里是从中间向左遍历，目的是为了让划分的左右两边序列能连接起来
temp+=nums[i];
if(s1
}
temp=0;
for(int i=mid+1;i<=right;i++){
temp+=nums[i];
if(s2
}
int msum = s1+s2;
return max(max(lsum,rsum),msum);
}
int main(){
int nums[] = {1,-5,2,3};
cout<
return 0;
}
如果觉得《利用分治算法求数列的最大子段和C语言 最大子段和（分治法）》对你有帮助，请点赞、收藏，并留下你的观点哦！
