UVA - 108 Maximum Sum 求子矩阵的最大和

题目大意：给出一个矩阵，求出这个矩阵中的子矩阵的最大和

解题思路：和UVA 507的题目类似，只不过这次是个矩阵了，换个角度思考，将这个二维数组转换成一维数组思考，用sum存储该列的前N个数字的和，如，sum［3］［1］就是第一列的前三个数字的和，这样就可以将其想象成一维的最大连续和了，在枚举行，求其最大的和，这样列就成了前进的标准了

#include<cstdio>
#include<cstring>
const int maxn = 100 + 5;
int arr[maxn][maxn];

int main() {
	int num,temp;
	memset(arr,0,sizeof(arr));
	while(scanf("%d", &num) != EOF && num) {
		for(int i = 1 ; i <= num; i++)
			for(int j = 1; j <= num; j++) {
				scanf("%d", &temp);
				arr[i][j] = arr[i-1][j] + temp;
			}

		int sum = arr[1][1];	
		for(int i = 0; i <= num; i++)
			for(int j = i+1; j <= num; j++) {
				temp = 0;
				for(int k = 1; k <= num ; k++) {
					if(temp < 0) 
						temp = arr[j][k] - arr[i][k];
					else 
						temp = temp + arr[j][k] - arr[i][k];
					if(temp > sum)
						sum = temp;
				}				
			}
		printf("%d\n",sum);
	}
	return 0;
}