最长字段和-动态规划

#include "stdafx.h"
#include "iostream"
#define num 100
using namespace std;

int a[num];

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

int MaxSum(int n,int& start,int& end)
{
	int sum=0;
	int b=0;
	int begin=0;
	for(int i=1;i<=n;i++)
	{
		if(b>0)
			b+=a[i];
		else
		{
			b=a[i];
			begin=i;
		}
		if(b>sum)
		{
			sum=b;
			start=begin;
			end=i;
		}
	}
	
	return sum;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int start=0;
    int end=0;
	a[1]=1;a[2]=-3;a[3]=7;a[4]=8;a[5]=-4;a[6]=12;a[7]=-10;a[8]=6;
	int x=MaxSum(8,start,end);
	cout<<"最长字段和："<<x<<" start:"<<start<<" end:"<<end<<endl;
	system("pause");
	return 0;
}