最大子段和

最大子段和问题是将一个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;
}

最后

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