林政-5分.txt

来自「这是很不错的计算机算法」· 文本 代码 · 共 77 行

//
//学号:040000103
//姓名:林政
//
#include < iostream.h > 
#include < fstream.h >
#include < stdio.h > 
ofstream out_file("output.txt"); //输出文件
int MaxSum(int n,int * a);
int MaxSum2(int m,int n,int * * a);
//////////////////////////////////////////////////
void main()
{
    int i , j; //循环变量
    int m , n; //矩阵行、列
    int * * a ; //序列x

    ifstream in_file("input.txt",ios::nocreate); //读取文件
    if (in_file.fail())
    {
	cerr << " 文件读取错误!";
	return; //如果没有输入文件，则返回错误
    }

    in_file >> m >> n ; //读取矩阵行、列
    m = m + 1;
    n = n + 1;
// 
// 读取数字到序列a中 
// 
    a = new int * [m];
    for (i = 1;i < m; i++) 
    {
	a[i] = new int[n];
	for (j = 1 ; j < n ; j++) 
	{
	    in_file >> a[i][j];
	}
    }
//  end读取序列
    out_file << MaxSum2(m-1,n-1,a) << endl;
    for (i = 1; i < m; i++) delete[] a[i];
}
//////////////////////////////////////////////////
int MaxSum(int n,int * a)
{
    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 MaxSum2(int m,int n, int * * a)
{
    int sum = 0;
    int * b = new int[n+1];
    for (int i = 1;i <= m;i++)
    {
	for (int k = 1;k <= n;k++) b[k] = 0;
	for (int j = i;j <= m;j++) 
	{
	    for (int k =1;k <= n;k++)
	    {
		b[k] += a[j][k];
	    } 
	    int max = MaxSum(n,b);
	    if (max > sum) sum = max;
	}
    }
    return sum;
}