【算法设计与分析】暴力、分治、动态规划——最大子段和问题

问题描述

给定由n个整数(可能有负整数)组成的序列(a₁,a₂,…a_n),求该序列子段和的最大值，当所有整数均为负整数时，其最大子段和为0

暴力

1.从第一个数开始计算长度为1、2……n的字段和，将这一段的最大字段和保存起来
2.再从第2个数开始计算长度为1、2……n-1的字段和，将这一阶段的最大字段和与前一阶段求得的最大字段和比较，取最大的保存下来
3.以此类推，最后保存的即为整个程序的最大字段和。

代码如下

int MaxSubStringSum_BF(vector<int> v)
{
	int n = v.size(),maxSum=0,sum=0;
	for(int i=0;i<n;i++)
	{
		sum =0;
		for(int j=i;j<n;j++)
		{
			sum = sum + v[j];
			if(sum>maxSum) maxSum=sum;
		}
	}
	return maxSum;
}

分治

1.将子段分成长度相等的两段
2.求出左边子段的最大字段和
3.求出右边子段的最大字段和
4.求出横跨左右两段的最大字段和
5.求出三者中的最大值即解

代码如下

int MaxSubStringSum_FenZhi(vector<int> v,int m,int n)
{
	int sum =0;
	if(n-m==1)
	{
		if(v[m]>0) sum = v[m];
		else sum =0;
	}
	else
	{
		int mid = (m+n)/2;
		int lsum = MaxSubStringSum_FenZhi(v,m,mid);
		int rsum = MaxSubStringSum_FenZhi(v,mid,n);
		int ll=0,lmax=0;
		for(int i=mid-1;i>=m;i--)
		{
			ll += v[i];
			if(lmax<ll) lmax = ll;
		}
		int rr=0,rmax=0;
		for(int i=mid;i<n;i++)
		{
			rr += v[i];
			if(rmax<rr) rmax = rr;
		}
		sum = lmax+rmax;
		if(sum<lsum) sum = lsum;
		if(sum<rsum) sum = rsum;
	}
	return sum;
}

动态规划

1.temp表示以v[i-1]结尾的子串的最大子段和，如果temp>=0,那么以v[i]结尾的子串的最大子段和一定是temp+v[i];
2.如果temp<0,那么以v[i]结尾的子串的最大子段和为v[i];
3.从头遍历一次记录最大的temp即为最大子段和；

代码如下

int MaxSubStringSum_dp(vector<int> v)
{
	int n = v.size();
	int maxSum =0,temp=0;
	for(int i=0;i<n;i++)
	{
		if(temp>=0) temp+=v[i];
		else temp= v[i];
		if(maxSum<temp) maxSum=temp; 
	}
	return maxSum;
} 
int main()
{
	int k;
	vector<int> v;
	while(cin >> k && k!=-1)
		v.push_back(k);
	cout << "暴力法得到的结果：" << MaxSubStringSum_BF(v)<<endl;
	cout << "分治法得到的结果：" << MaxSubStringSum_FenZhi(v,0,v.size()) << endl;
	cout << "动态规划法得到的结果：" << MaxSubStringSum_dp(v) << endl;	
	return 0;
} 

/*
1 -3 2 3 -4 23 33 -2 6 -1
*/

结果如下