宋晓秋-6分.txt

这是很不错的计算机算法

#include < iostream.h > 
#include < fstream.h >
#include < stdio.h >

int MaxSum(int m,int n,int *a)
{
  int *b=new int[n+1];
  int *c=new int[n+1];
  b[0]=0;
  c[1]=0;

  for(int i=1;i<=m;i++)
      { b[i]=b[i-1]+a[i];
	c[i-1]=b[i];
	int max=b[i];
	for(int j=i+1;j<=i+n-m;j++)
	      { b[j]=b[j-1]>c[j-1]?b[j-1]+a[j]:c[j-1]+a[j];
		c[j-1]=max;
		if(max<b[j])
		    max=b[j]; }
	c[i+n-m]=max; }

/*如果最大m子段和为负值时要求输出负值本身，请使用本段替代下面三行程序代码!
  int sum=b[m];
  for(int j=m+1;j<=n;j++)
		sum=sum>b[j]?sum:b[j];
*/

  int sum=0;
  for(int j=m;j<=n;j++)
	if(sum<b[j])   sum=b[j];

  return sum;
}


ofstream out("output.txt");
int temp;

int main()
	{int temp;   

	ifstream in("input.txt");
	if(in.fail())
		{	cout<<"the input.txt is not exist!";
			return 0;	}
	int m,n;
	in>>n>>m;
	int *a=new int [n+1];
//	a[0]=0;//
	for(int i=1;i<=n;i++)
	       in>>a[i]; 

	if(n<m || m<1) return 0;
	temp=MaxSum(m,n,a);

	ofstream out("output.txt");
	out<<temp;
	
	delete[] a;
	return 1;
}