tothemax.cpp

最大子矩阵和问题

// ToTheMax.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream.h>
#include "IO.cpp"
#include <stdlib.h>

int LineMax(const int line[],int num)//一维的最大子矩阵和
{
	int maxarr[100];
	maxarr[0]=line[0];
	for(int i=1;i<num;i++)
	{
		int a=maxarr[i-1]+line[i];
		int b=line[i];
		maxarr[i]=a>b?a:b;
	}
	int max=maxarr[0];
	for(i=1;i<num;i++)
	{
		if(maxarr[i]>max)
		{
			max=maxarr[i];
		}
	}
	return max;
}

int LineMax2(const int line[],int num)
{
	int max=-2147483648;
	int cur=0;
	for(int i=0;i<num;i++)
	{
		if(cur>0)
		{
			cur+=line[i];
		}
		else
		{
			cur=line[i];
		}
		if(cur>max)
			max=cur;
	}
	return max;
}

int main(int argc, char* argv[])
{
	//输入文件
	//char path1[100]="G:\\ACM题库\\problem\\data\\1050\\mydata.in";
	char path1[100]="G:\\ACM题库\\problem\\data\\1050\\maxsum.in";
	//输出文件
	//char path2[100]="D:\\Program Files\\Microsoft Visual Studio\\MyProjects\\ACM\\ToTheMax\\Output\\mydata.out";
	char path2[100]="D:\\Program Files\\Microsoft Visual Studio\\MyProjects\\ACM\\ToTheMax\\Output\\maxsum.out";
	//答案文件
	char path3[100]="G:\\ACM题库\\problem\\data\\1050\\mydata.out";
	InPut cin(path1);
	OutPut cout(path2);

	////////////////
	int arr[100][100];
	int n=0;//矩阵的行数和列数
	cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>arr[i][j];
		}
	}
	int max=-2147483648;
	int b[100];
	for(i=0;i<n;i++)
	{
		for(int s=0;s<n;s++)//初始化
		{
			b[s]=0;
		}
		for(int j=i;j<n;j++)
		{
			for(int k=0;k<n;k++)
			{
				b[k]+=arr[j][k];
			}
			int temp=LineMax(b,n);
			if(temp>max)
			{
				max=temp;
			}
		}
	}
	cout<<max<<endl;
	return 0;
}