Giả sử mảng con có tổng lớn nhất được giới hạn bởi $2$ hàng $u \le v$ và cột $i, j$.
Nếu ta duyệt $2$ vòng for thử $u$ và $v$, ta cần chọn ra cột $i$ và $j$ sao cho tổng bảng con được giới hạn bởi hàng $u, v$ và cột $i, j$ là lớn nhất
Gọi $b_i$ là tổng các số trong cột $i$ và được giới hạn bởi hai hàng $u, v$ này.
$b_i = a[u][i] + a[u+1][i] + ... + a[v-1][i] + a[v][i]$, thì bài toán tìm mảng con tốt nhất giới hạn bởi $2$ hàng $u, v$ sẽ trở thành bài toán tìm đoạn con có tổng lớn nhất trên mảng $1$ chiều: [Mảng con có tổng lớn nhất](https://marisaoj.com/problem/60)
Code mẫu:
```cpp
#include<bits/stdc++.h>
#define maxn 502
using namespace std;
long long ans;
int n, m, a[maxn][maxn];
long long b[maxn];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
cin >> a[i][j];
for (int u=1; u<=n; u++) {
for (int i=1; i<=m; i++) b[i] = 0;
for (int v=u; v<=n; v++) {
long long s = 0;
for (int i=1; i<=m; i++) {
b[i] += a[v][i];
s += b[i];
if (s < 0) s = 0;
ans = max(ans, s);
}
}
}
cout << ans;
}
```
Chi tiết cách làm có thể xem tại đây: https://youtu.be/fYwhI-Onp1k
YugiHacker
Created at
1 likes