编程之美---子矩阵之和的最大值
把二维转化为一维,再利用求最大子序列的方法求最大子矩阵.
#include<stdio.h>#include<stdlib.h>#include<string.h>#include<assert.h>#define max(a, b) ((a) > (b) ? (a) : (b))const int neginf = 0x80000001;int a[100][100] = {0};int getMaxSum(int *b, int n){int curSum = 0;int maxSum = neginf;for(int i=0; i<n; i++){if(curSum < 0)curSum = 0;curSum += b[i];maxSum = max(maxSum, curSum);}return maxSum;}int * getSeqMatrix(int s, int e, int n){int *b = new int[n];for(int i=0; i<n; i++)b[i] = 0;for(i=0; i<n; i++){for(int j=s; j<=e; j++){b[i] += a[j][i];}}return b;}int getMaxMatrix(int n){int curSum = 0;int maxSum = neginf;for(int i=0; i<n; i++){for(int j=i; j<n; j++){int *b = getSeqMatrix(i, j, n);curSum = getMaxSum(b, n);maxSum = max(curSum, maxSum);delete []b;}}return maxSum;}void test(){int n;while(scanf("%d", &n)!=EOF){if(n == 0) break;for(int i=0; i<n; i++){for(int j=0; j<n; j++)scanf("%d", &a[i][j]);}int ret = getMaxMatrix(n);printf("%d\n", ret);}}int main(){test();return 0;}