# 【題解】UVA 00836 Largest Submatrix

【題目敘述】https://vjudge.net/problem/UVA-836
【解題想法】DP: Max 2D Range Sum

```//【解題想法1】前綴
#include <iostream>
using namespace std;

int t, n, a[30][30], mx;
string s;

int main(){
cin >> t;
while (t--){
cin >> s;
n = s.length();
for (int j = 1; j <= n; j++){
a[1][j] = s[j-1]-'0';
a[1][j] += a[1][j-1];
}
for (int i = 2; i <= n; i++){
cin >> s;
for (int j = 1; j <= n; j++){
a[i][j] = s[j-1]-'0';
a[i][j] += a[i][j-1];
}
}
mx = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
a[i][j] += a[i-1][j];
for (int k = 0; k < i; k++){
for (int l = 0; l < j; l++){
int tmp = a[i][j];
tmp -= a[i][l];
tmp -= a[k][j];
tmp += a[k][l];
if (tmp == (i-k)*(j-l)) mx = max(mx, tmp);
}
}
}
}
cout << mx << "\n";
if (t != 0) cout << "\n";
}
}
```
```//【解題想法2】把 0 設為 -INF
#include <iostream>
using namespace std;

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int T, N;
string s;
bool first = true;
cin >> T;
while (T--){
int a[26][26] = {0};
N = 26;
for (int i = 0; i < N; i++){
cin >> s;
for (int j = 0; j < N; j++){
if (s[j] == '0') a[i][j] = -1000; //-INF
else a[i][j] = 1;
}
N = s.size();
}
int row[26] = {0};
int mx = 0;
for (int i = 0; i < N; i++){
for (int k = 0; k < N; k++){
row[k] = 0;
}
for (int j = i; j < N; j++){
for (int k = 0; k < N; k++){
row[k] += a[k][j];
}
int sum = 0;
for (int k = 0; k < N; k++){
sum += row[k];
mx = max(mx, sum);
if (sum < 0) sum = 0;
}
}
}
if (first) first = false;
else cout << "\n";
cout << mx << "\n";
}
return 0;
}
```
```//【解題想法3】參考 TIOJ 1063 . 最大矩形(Area)
// https://yuihuang.com/tioj-1063/
#include <iostream>
using namespace std;

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int T, N;
string s;
bool first = true;
cin >> T;
while (T--){
int a[26][26] = {0};
cin >> s;
N = s.size();
for (int j = 0; j < N; j++){
a[0][j] = s[j] - '0';
}
for (int i = 1; i < N; i++){
cin >> s;
for (int j = 0; j < N; j++){
a[i][j] = s[j] - '0';
}
}
int len[26] = {0};
int mx = 0, mn, k;
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
len[j] = a[i][j] ? len[j] + 1 : 0;
mx = max(mx, len[j]);
for (k = j-1, mn = len[j]; k >= 0 && a[i][k] == 1; k--){
mn = min(mn, len[k]);
mx = max(mx, mn * (j - k + 1));
}
}
}
if (first) first = false;
else cout << "\n";
cout << mx << "\n";
}
return 0;
}
```