最大子矩阵
Problem Description
给你一个m×n的整数矩阵，在上面找一个x×y的子矩阵，使子矩阵中所有元素的和最大。
Input
输入数据的第一行为一个正整数T，表示有T组测试数据。每一组测试数据的第一行为四个正整数m,n,x,y（0<m,n<1000 AND 0<x<=m AND 0<y<=n），表示给定的矩形有m行n列。接下来这个矩阵，有m行，每行有n个不大于1000的正整数。
Output
对于每组数据，输出一个整数，表示子矩阵的最大和。
Sample Input
1 4 5 2 2 3 361 649 676 588 992 762 156 993 169 662 34 638 89 543 525 165 254 809 280
Sample Output
暴力解法: 类似于求最大子列和 初始当然定义一个maxer 两层for (i,j)循环先输入这个数组，然后再套两层for循环 初始设定 和sum=0 从第a[i-x+1][j-y+1]处遍历到a[i][j]，并且遍历的时候把和求出来 这个和就是 长度为x，宽为y的一个矩阵和。 (a[i][j]为右下角顶点) 如果这个和比之前的maxer要大，那么它就是要求的矩阵最大和，并赋值为maxer 复杂度 n^4
#include<iostream> using namespace std; int main() { int a[100][100]; int m, n, x, y; int T; cin >> T; int maxer; while (T--){ maxer = -1; memset(a, 0, sizeof(a)); cin >> m >> n >> x >> y; for (int i = 1; i <= m; i++){ for (int j = 1; j <= n; j++){ cin >> a[i][j]; int sum = 0; if (i >= x&&j >= y){ for (int l = i - x + 1; l <= i; l++){ for (int k = j - y + 1; k <= j; k++) sum += a[l][k]; } } maxer = max(maxer, sum); } } cout << "max=" << maxer << endl; } system("pause"); return 0; }