最大子段和动态规划算法.cpp

来自「动态规划解一系列经典问题」· C++ 代码 · 共 32 行

//最大子段和动态规划算法

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#define N 10

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

void main()
{
	srand(time(0));
	int i,a[N];
	for(i=0; i<N; i++)
	{
		a[i]=rand()%999-400;
		cout<<a[i]<<'\t';
	}
	cout<<endl;
	int k=MaxSum(N, a);
	cout<<k<<endl;
}