给定由n个整数(可能为负整数)组成的序列a1,a2, a3… , an, 寻找它的某个连续子段,使得其和最大。例如( -2,11,-4,13,-5,-2 )最大子段是{ 11,-4,13 }其和为20。

1、最大字段和问题的简单算法

(1)枚举法求解:
以a[0]开始: {a[0]}, {a[0],a[1]},{a[0],a[1],a[2]}……{a[0],a[1],……a[n]}共n个
以a[1]开始: {a[1]}, {a[1],a[2]},{a[1],a[2],a[3]}……{a[1],a[2],……a[n]}共n-1个
……
以a[n]开始:{a[n]}共1个

#include<iostream> 
using namespace std;


int maxSum(int n, int a[], int &besti, int &bestj){
	
	int sum = 0;
	for(int i= 0; i < n; i++)	{
		
		int thisSum = 0;
		for(int j = i; j < n; j++){
			
			thisSum += a[j];
			if(thisSum > sum){
			
				sum = thisSum;
				besti = i;
				bestj = j;
			}
		}
		
	}
	return sum;
}

int main(){
	
	int a[] = {-2,11,-4,13,-5,-2,};
 
	for(int i=0; i<6; i++)
	{
		cout<<a[i]<<" ";
	}
	
	int besti,bestj;
	 
	cout<<endl;
	cout<<"数组a的最大连续子段和为:a["<<besti<<":"<<bestj<<"]:"<<maxSum(6,a,besti,bestj)<<endl;
	
	return 0;
}

在这里插入图片描述

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]的最大字段和为在这里插入图片描述
    ,且1<=i<=n/2,n/2+1<=j<=n。

可用递归方法求得情形1、2。对于情形3,可以看出a[n/2]与a[n/2+1]在最优子序列中。因此可以在a[1:n/2]中计算在这里插入图片描述
,并在a[n/2+1:n]中计算在这里插入图片描述。则s1+s2即为出现情形3时的最优值。

#include<iostream>
using namespace std;

int maxSubSum(int a[], int left, int right){

	int sum = 0;
	if(left == right){
		sum = a[left]>0 ? a[left] : 0;
	}
	else{
		
		int center = (left + right) / 2;
		int leftSum = maxSubSum(a, left, center);
		int rightSum = maxSubSum(a, center + 1, right);

		int s1 = 0;
		int lefts = 0;
		for(int i = center; i >= left; i--){
			
			lefts += a[i];
			if(lefts > s1) s1 = lefts;
		}
	
		int s2 = 0;
		int rights = 0;
		for(int i = center + 1; i < right; i++){
			
			rights += a[i];
			if(rights > s2)	s2 = rights;
		}
		sum = s1 + s2;
		if(sum < leftSum) sum = leftSum;	
		if(sum < rightSum) sum = rightSum;
	}
	return sum;
}

int maxSum(int a[], int n){
	return maxSubSum(a, 0, n - 1);
}

int main(){
	
	int a[] = {-2,11,-4,13,-5,-2,};
 //           left             right
	for(int i= 0; i < 6; i++)
	{
		cout<<a[i]<<" ";
	}	 
	cout<<endl;
	cout<<"数组a的最大连续子段和为:" << maxSum(a, 6)<<endl;
	return 0;
}

在这里插入图片描述
O(nlogn)

3、动态规划算法:

#include<iostream>
using namespace std;

int maxSum(int a[], int n){
	
	int sum = 0;
	int b = 0;
	
	for(int i = 0; i < n; i++){
		
		if(b > 0)
			b += a[i]else
			b = a[i];
		
		if(b > sum)
			sum = b;
	}
	return sum;	
}

int main(){
	
	int a[] = {-2,11,-4,13,-5,-2,6};

	for(int i= 0; i < 7; i++)
	{
		cout<<a[i]<<" ";
	}	 
	cout<<endl;
	cout<<"数组a的最大连续子段和为:" << maxSum(a, 7)<<endl;
	return 0;
}

在这里插入图片描述

4、最大子段和问题动态规划算法推广:

一、最大子矩阵和:

二、最大m子段和问题:

Logo

为开发者提供学习成长、分享交流、生态实践、资源工具等服务,帮助开发者快速成长。

更多推荐