最大子段和

Contents

1. 1. 动态规划方程
2. 2. 最大子段和核心算法
3. 3. 全部代码

给定n个整数组成的序列a1,a2,…an, 求子段和ai+ai+1+…+aj（子段可为空集）的最大值。

动态规划方程

b[j]=max(b[j-1]+a[j],a[j]) 1<=j<=n

最大子段和核心算法

int maxsum(int *a,int n)
{
	int b=0,sum=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;
}

全部代码

#include<iostream>
using namespace std;
int Maxsum(int n,int *a)
{
	int sum=0,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 main()
{
	int m;
	cin>>m;
	for(int t=0;t<m;t++)
	{
		int *n=new int(m);
		for(int j=0;j<m;j++)
		{
		    cin>>n[j]; 
		int *p=new int(n[j]);
		for(int i=1;i<=n[j];i++)
		    cin>>p[i];
		int t=Maxsum(n[j],p);
		cout<<t<<endl;
		}
	}
}