【題解】UVA 00836 Largest Submatrix

//【解題想法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;
}