最大子段和例题_最短路径四大算法

最大子段和例题_最短路径四大算法给定由n个整数(可能为负整数)组成的序列a1,a2,a3…,an,寻找它的某个连续子段,使得其和最大

给定由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子段和问题:

今天的文章最大子段和例题_最短路径四大算法分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/78311.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注