poj 1050 To the Max

http://162.105.81.212/JudgeOnline/problem?id=1050

找出最大子矩阵的和

用一个数组b来存放竖列的值,(具体哪列到哪列与j,k的值有关)

然后累加的同时记录下最大值, 如果和还>0继续累加

#include<iostream>
using namespace std;
int a[100][100];
int b[100];
int main()
{
//freopen("in.txt", "r", stdin);
	int n, i, j, k;
	int s, sum, max;
	scanf("%d", &n);
	for(i=0; i<n; i++)
		for(j=0; j<n; j++)
			scanf("%d", &a[i][j]);
	s=0;
	for(i=0;i<n;i++)
	{
		memset(b, 0, sizeof(b));
		for(j=i; j<n; j++)
		{
			for(k=0; k<n; k++)
				b[k] += a[j][k];
			sum = 0, max = 0;
			for(k=0; k<n; k++)
			{
				if(sum + b[k] > 0)
					sum += b[k];
				else
					sum = b[k];
				if(sum > max)
					max = sum;
			}
			if(max > s)
				s = max;
		}
	}
	printf("%d/n", s);
	return 0;
}