ACWing-126 最大的和 题解

题目大意

给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为1 * 1或更大的连续子阵列。

矩形的总和是该矩形中所有元素的总和。

在这个问题中，具有最大和的子矩形被称为最大子矩形。

解题思路

这个题目有个类似的，但是是一维的。

懂了那个之后，这个题就会做了。

枚举上下界，然后对于其中的数据，做类似一维的即可。

对于每一个点，判断前一个点之前的最大和是否为正数，然后正数才相加。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define endl '\n'
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

int num[110][110];

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b, ll mod) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans = (ans * a) % mod;
		a = (a * a) % mod, b >>= 1;
	}
	return ans % mod;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int n; cin >> n;
	rep(i, 1, n) {
		rep(j, 1, n) {
			int x; cin >> x;
			num[i][j] = num[i - 1][j] + x;
		}
	}
	int ans = -1e9;
	rep(i, 1, n) {
		rep(j, i, n) {
			int res = 0;
			rep(k, 1, n) {
				int t = num[j][k] - num[i - 1][k];
				res = max(res, 0) + t;
				ans = max(ans, res);
			}
		}
	}
	cout << ans << endl;
	return 0;
}