蓝桥杯历届试题-最大子阵 （C++代码）

解题思路:

        二维压缩成一维的最大子段，枚举。

参考代码:

#include<bits/stdc++.h>
#define Inf 0x3F3F3F3F
using namespace std;

const int SIZE = 502;
int datas[SIZE][SIZE];

int main() {
	int M, N, tmp; scanf("%d%d", &M, &N);
	for (int i1 = 1; i1 <= M; i1++)
		for (int i2 = 1; i2 <= N; i2++) {
			scanf("%d", &tmp);
			datas[i1][i2] = datas[i1 - 1][i2] + tmp;
		}

	int ans = -Inf, nowValue;
	for (int line = 1; line <= M; line++) {
		for (int D = line; D <= M; D++) {
			int tmp = -Inf;
			for (int pos = 1; pos <= N; pos++){
				nowValue = datas[D][pos] - datas[line - 1][pos];

				tmp = max(tmp + nowValue, nowValue);
				if (tmp > ans)
					ans = tmp;
			}
		}
	}
	cout << ans;
}