#DP #MIS #MIS2D #SubRectangle #UVa #Solved

836 - Largest Submatrix.cpp

//https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=777
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 15;
const int OO = 1e4;
int dp[110][110];
int n;

int main() {
    int t;
    cin>>t;
    while(t--) {
        int x;
        string s;
        cin>>s;
        n = s.length();
        //cout << n << endl;
        for(int i= 1; i <= n; i++) {
            for(int j= 1; j <= n; j++) {
                if(s[j-1] == '0') x = -1*OO;
                else x = 1;
                //cout << x << endl;
                dp[i][j] = dp[i][j-1] + x;
            }
            if(i!=n) {
            cin>>s;}
        }
        int best = 0, bestOfBest = 0 /* LOL */ , sum = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = i; j <= n; j++) {
                sum = 0;
                for(int k = 1; k <= n; k++) {
                    x = dp[k][j] - dp[k][i-1];
                    //cout << x << endl;
                    if(sum < 0) {
                        sum = x;
                    } else {
                        sum += x;
                    }
                    if(sum > best) best = sum;
                }
                if(best > bestOfBest) bestOfBest = best;
            }
        }

        cout << bestOfBest << endl;
        if(t != 0) cout << endl;
    }
    return 0;
}