1.


/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 836 Largest Submatrix
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=777
*
* @author Burgmair Stefan
* @author YYY
* @version 1.0, 12/04/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.148
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main
{
public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int nmbrOfMatrices = Integer.parseInt(reader.readLine());
String readline = reader.readLine();
int c = 0;

ArrayList<String> input = new ArrayList<String>();
int[] output = new int[nmbrOfMatrices];

for (int i = 0; i < nmbrOfMatrices; i ++)
{
do
{
readline = reader.readLine();

if (!readline.equals(""))
{
input.add(readline);
}
}while (reader.ready() && !readline.equals(""));

int [][] map = new int [input.size()][input.size()];

for (int o = 0; o < input.size(); o++)
{
for (int p = 0; p < input.get(o).length(); p++)
{
map[o][p] = Integer.parseInt ("" + input.get(o).charAt(p));
}
}

output[c] = checkMatrx(map);
c++;
input.clear();
}

for (int i = 0; i < output.length; i++)
{
if (i != 0)
System.out.println();
System.out.println(output[i]);
}
}

private static int checkMatrx(int[][] a){
int maxValue = 0;
int depth = 0;
int maxDepth = 0;

for (int col = 0; col < a.length; col++)
{
for (int row = 0; row < a.length; row++)
{
//System.out.println("From: " + col +"|"+ row);
for (int x = col; x < a.length; x++)
{
for (int y = row; y < a.length; y++)
{
if (a[x][y] == 0 | y == a.length-1)
{
if (a[x][y] == 1 && y == a.length-1)
y++;

if (x - col == 0)
{
depth = y - row;
maxDepth = depth;
}
else if (y - row > maxDepth)
depth = maxDepth;
else
{
depth = y - row;
maxDepth = depth;
}

//System.out.println(x + "/" + col);
if (maxValue < depth * (x - col + 1))
maxValue = depth * (x - col + 1);
//System.out.println("Break inner: " + x +"|"+ y + " at: " + depth);
break;
}
}
if (a[x][row] == 0)
{
//System.out.println("Break outer: " + x +"|"+ row);
break;

}
}
}
}

return maxValue;
}
}



-------------------------------------------------------------
1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 836 - Largest Submatrix
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=777
*
* @author Evgeni Pavlidis
* @version 1.0, 06/05/2010
*
* Method : Kadane - Max substring
* Status : Accepted
* Runtime: 0.112
*/

import java.io.*;
import java.util.*;

class Main {

private static String[] m = new String[26];

public static void main(String...args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int testCases = Integer.parseInt(reader.readLine());

int[][] rowSum = new int[27][27];
int n, sum = 0, max;

for(int tc = 0; tc < testCases; tc++)
{
if(tc > 0)
System.out.println();

// read input
reader.readLine();
m[0] = reader.readLine();
n = m[0].length();
for(int r = 1; r < n; r++)
m[r] = reader.readLine();


// accumulate row sums
for(int r = 0; r < n; r++, sum = 0)
for(int c = 0; c < n; c++)
rowSum[r][c+1] = sum = sum + (m[r].charAt(c) == '0'? -1000: 1);


// find max substring (submatrix)
max = 0;
for(int c1 = 1; c1 <= n; c1++)
for(int c2 = c1; c2 <= n; c2++, sum = 0)
for(int r = 0; r < n; r++)
{
sum += rowSum[r][c2] - rowSum[r][c1-1];

if(sum < 0)
sum = 0;

if(sum > max)
max = sum;
}

System.out.println(max);
}
}
}