求最大子矩阵（子矩阵无大小要求）dp

总时间限制:  1000ms  内存限制:  65536kB 描述 已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。 比如，如下4 * 4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 的最大子矩阵是 9 2 -4 1 -1 8 这个子矩阵的大小是15。 输入 输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N ²个整数，整数之间由空白字符分隔（空格或者空行）。已知矩阵中整数的范围都在[-127, 127]。 输出 输出最大子矩阵的大小。 样例输入 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 样例输出 15 题意：把二维的问题转化为一维的最大子序列问题 #include <cstdlib> #include <iostream> using namespace std; const int MAX = 101; int value[MAX][MAX] = {{0,0}}; int subMaxSum(int a[], int n) //找到一维数组中最大子序列 { int sum = 0, b = 0; for(int i=0; i<n; i++) { if(b > 0) b += a[i]; else b = a[i]; if(b > sum) sum = b; } return sum; } int maxSum(int n) { int sum = 0, max = 0; for(int i=0; i<n; i++) //i控制从第几行开始压缩，每次都是从第i行压缩到最后一行 { int b[MAX] = {0}; //i每变化一次，b数组就要重新赋值 for(int j=i; j<n; j++) { for(int k=0; k<n; k++) //压缩矩阵 b[k] += value[j][k]; sum = subMaxSum(b, n); if(sum > max) max = sum; //max存到当前状态，子矩阵的最大值 } } return max; } int main() { int n; cin >> n; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) cin >> value[i][j]; } cout << maxSum(n); return 0； }