我是靠谱客的博主 迷路钢笔,这篇文章主要介绍最大子段和,现在分享给大家,希望可以做个参考。

最大子段和问题是将一个n个整数的序列a[1],a[2]….a[n]中字段a[first]….a[last]之和,(1<=first<=last<=n)求这些子段和中最大的。 

例如(a[1],a[2],a[3],a[4],a[5],a[6])=(-2,11,-4,13,-5,-2)时,最大子段和为20,子段为a[2],a[3],a[4]。


#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[101];

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<n;i++)
			cin>>a[i];
		
		int b=0,sum=0,begin,besti,bestj;
		
		for(int i=0;i<n;i++)
		{
			if(b>0)
				b+=a[i];
			else
			{
				b=a[i];
				begin = i; 
			}	
			if(b>sum)
			{
				sum=b;
				besti = begin;
				bestj = i;
			}
		}
		for(int i=besti;i<=bestj;i++)
		cout<<a[i]<<" ";
	}
	return 0;
}


最后

以上就是迷路钢笔最近收集整理的关于最大子段和的全部内容,更多相关最大子段和内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(63)

评论列表共有 0 条评论

立即
投稿
返回
顶部