《分治中的典型题型-求字符串的最大子段和》

问题二：最大连续和（字符串的最大连续子串的和）
比如给了一串字符串[1,-2,3,10,-4,7,2,-5]让你求最大的子字符串的和经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18。
解答：针对最大子段和这个具体问题本身的结构，我们还可以从算法设计的策略上对上述O(n^2)计算时间算法进行更进一步的改进。从问题的解结构也可以看出，它适合于用分治法求解。
如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n],分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种情况：
（1） a[1:n]的最大子段和与a[1:n/2]的最大子段和相同
（2） a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同
（3） a[1:n]的最大子段和为a[i]+…+a[j]，并且1<=i<=n/2，n/2+1<=j<=n。
对于（1）和（2）两种情况可递归求得，但是对于情况（3），容易看出a[n/2]，a[n/2+1]在最大子段中。因此，我们可以在a[1:n/2]中计算出s1=max(a[n/2]+a[n/2-1]+…+a[i]),0<=i<=n/2，并在a[n/2+1:n]中计算出s2= max(a[n/2+1]+a[n/2+2]+…+a[i])，n/2+1<=i<=n。则s1+s2为出现情况（3）的最大子段和。
代码实现

#include <iostream>
using namespace std;
int main()
{
	int n,A[100];
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>A[i];
	}
	int ans=A[1];
	for(int i=1;i<=n;++i)
	{
		for(int j=i;j<=n;++j)
		{
			int sum=0;
			for(int x=i;x<=j;++x)
			{
				sum+=A[x];
			}
			if(ans<sum)
			{
				ans=sum;
			}
		}
	}
	cout<<ans<<endl;
	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