maxm.cpp

给定由n 个整数(可能为负整数)组成的序列1 a

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

int MaxSum(int m,int n, int * a)
{
	if (n < m || m < 1) return 0;
	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;
	}
	int sum = 0;
	for (int j = m;j <= n; j++)
		if (sum < b[j]) sum = b[j];
		
		return sum;
}

void main()
{
	int i; 
	int m , n; 
	int * a ; 

	ifstream in("input.txt"); 
	if (in.fail())
	{
		cerr << "open file error!!!";
		return; 
	}

	in >> n >> m ; 
	n = n + 1;
	a = new int[n];
	for (i = 1 ; i < n ; i++)
	{
		in >> a[i];
	}
	
	ofstream out("output.txt");

	out << MaxSum(m,n,a) << endl;

	delete[] a;

	in.close();
	out.close();
}