分治法求解最大子段和问题_分治算法求最大子段和

分治法求解最大子段和问题

1.方法介绍
分治法:分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。
2.求解过程
分治法的求解过程分为三个阶段
1)划分:把规模为n的原问题划分为k个规模较小的子问题。
2)求解子问题:各个子问题和原问题的解法通常是相同的，可以用递归的方法求解各个子问题。
3)合并:把各个子问题的解合并起来。
3.问题描述
最大子段和问题:给定由n个整数组成的序列(a1,a2,…an),最大子段和问题要求该序列形如∑ak的最大值(找到的最大子段必须是连续的。)
4.源代码
测试用例:
a[]={-20, 11,-4, 13,-5,-2};

#include<stdio.h>
int Maxstring(int a[],int left,int right)//求解最大子段和 
{
	int sum=0,midsum=0,leftsum=0,rightsum=0;
	int center,s1,s2,lefts,rights;
	if(left==right)//若序列长度为1，则直接求解 
	  sum=a[left];
	else
	{
		center=(left+right)/2;//划分 
		leftsum=Maxstring(a,left,center);//递归求解左半段 
		rightsum=Maxstring(a,center+1,right);//递归求解右半段 
		s1=0,lefts=0;
		for(int i=center;i>=left;i--)
		{
			lefts+=a[i];
			if(lefts>s1)
			s1=lefts;
		}
		s2=0,rights=0;
		for(int j=center+1;j<=right;j++)
		{
			rights+=a[j];
			if(rights>s2)
			s2=rights;
		}
		midsum=s1+s2;
		if(midsum<leftsum)
		sum=leftsum;
		else
		sum=midsum;
		if(sum<rightsum)
		sum=rightsum;
	}
	return sum;
}
int main()
{
	int a[]={-20, 11,-4, 13,-5,-2};
	int sum=0;
	sum=Maxstring(a,0,5); 
	printf("求出的最大子段和为：%d",sum);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
'
运行
运行

5.最终结果