CareerCup

geeksforgeeks.org/?p=6257

But I guess you ca tweak it in such a way that the number of rows should not be equal to the number of columns....

If its the number of 1's which decided what constitutes the 'biggest' sub-matrix, shouldn't the answer be :
1 1 1 1
1 1 1 1
1 1 1 1
with 12 1's ?

<pre lang="java" line="1" title="CodeMonkey26657" class="run-this">
import java.util.Random;
class RectangleMatrix1 {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] aMatrix = new int[6][6];
Random r = new Random();
for (int i = 0; i < aMatrix.length; i++) {
for (int j = 0; j < aMatrix[0].length; j++) {
aMatrix[i][j] = r.nextInt(2);
}
}
for(int i=0;i<aMatrix.length;i++){
for(int j=0;j<aMatrix[0].length;j++){
System.out.printf( "%7d",aMatrix[i][j]);
}
System.out.println();
}
maximumRectangleMatrix(aMatrix);
}

private static void maximumRectangleMatrix(int[][] aMatrix) {
// TODO Auto-generated method stub
int[] oneD;
int maxX = 0;
int maxY = 0;
int sX = 0;
int sY = 0;
for (int i = 0; i < aMatrix.length; i++) {
oneD = new int[aMatrix[0].length];
for (int k = i; k < aMatrix.length; k++) {

int x = 0;
int y = k - i + 1;
int sy = 0;

int csy = 0;
int curmaxX = 0;

for (int j = 0; j < aMatrix[0].length; j++) {
oneD[j] = oneD[j] + aMatrix[k][j];
if (oneD[j] == y) {
sy = (x == 0) ? j : sy;
x++;
if (x > curmaxX) {
curmaxX = x;
csy = sy;
}
} else {
x = 0;
}
}
x = curmaxX;
x = (x == y) ? x - 1 : x;
if (x * y > maxX * maxY) {
maxX = x;
maxY = y;
sX = i;
sY = csy;
}
}
}
System.out.println();
System.out.printf("Rectangle SubMatrix Start From:{%d,%d}\n", sX, sY);
System.out.printf("Rectangle SubMatrix Size:{%dX%d}\n", maxX, maxY);
for (int i = sX; i < sX + maxY; i++) {
for (int j = sY; j < sY + maxX; j++) {
System.out.printf("%4d", aMatrix[i][j]);
}
System.out.println();
}
}
}
</pre><pre title="CodeMonkey26657" input="yes">1
2
10
42
11

</pre>

// Some correction to aboce Program 
import java.util.Random;
class RectangleMatrix1 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] aMatrix = new int[6][6];
		Random r = new Random();
		for (int i = 0; i < aMatrix.length; i++) {
			for (int j = 0; j < aMatrix[0].length; j++) {
				aMatrix[i][j] = r.nextInt(2);
			}
		}
                for(int i=0;i<aMatrix.length;i++){
			for(int j=0;j<aMatrix[0].length;j++){
				System.out.printf( "%7d",aMatrix[i][j]);
			}
			System.out.println();
		}		
                maximumRectangleMatrix(aMatrix);
	}

	private static void maximumRectangleMatrix(int[][] aMatrix) {
		// TODO Auto-generated method stub
		int[] oneD;
		int maxX = 0;
		int maxY = 0;
		int sX = 0;
		int sY = 0;
		for (int i = 0; i < aMatrix.length; i++) {
			oneD = new int[aMatrix[0].length];
			for (int k = i; k < aMatrix.length; k++) {

				int x = 0;
				int y = k - i + 1;
				int sy = 0;

				int csy = 0;
				int curmaxX = 0;

				for (int j = 0; j < aMatrix[0].length; j++) {
					oneD[j] = oneD[j] + aMatrix[k][j];
					if (oneD[j] == y) {
						sy = (x == 0) ? j : sy;
						x++;
						if (x > curmaxX) {
							curmaxX = x;
							csy = sy;
						}
					} else {
						x = 0;
					}
				}
				x = curmaxX;
				x = (x == y) ? x - 1 : x;
				if (x * y > maxX * maxY) {
					maxX = x;
					maxY = y;
					sX = i;
					sY = csy;
				}
			}
		}
		System.out.println();
		System.out.printf("Rectangle SubMatrix Start From:{%d,%d}\n", sX, sY);
		System.out.printf("Rectangle SubMatrix Size:{%dX%d}\n", maxX, maxY);
		for (int i = sX; i < sX + maxY; i++) {
			for (int j = sY; j < sY + maxX; j++) {
				System.out.printf("%4d", aMatrix[i][j]);
			}
			System.out.println();
		}
	}
}

can someone explain what are you doing in this in simple words

#include <iostream>
#include <algorithm>

using namespace std;

int main( void )
{
int N;
int t = 0;
int a[100][100];
int pr[100];
int S = 1<<31, s = 0, k, l, x1 = 0,x2 = 0,y1 = 0,y2 = 0,j;

cin >> N;

for( int i = 0; i < N; i++)
for( j = 0; j < N; j++)
cin >> a[i][j];

for( int z = 0; z < N; z++)
{
for(int i = 0; i < N; i++) pr[i] = 0;

for(int x = z; x < N; x++)
{
t = 0;
s = 1<<31;
j = 0;
k = 0; l = 0;
for(int i = 0; i < N; i++)
{
pr[i] = pr[i] + a[x][i];
t = t + pr[i];
if( t > s)
{
s = t;
k = i;
l = j;
}
if( t < 0 )
{
t = 0;
j = i + 1;
}
}
if( s > S)
{
S = s;
x1 = x;
y1 = k;
x2 = z;
y2 = l;
}
}
}

cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
cout << S;

return 0;
}
kadane algorithm

algo plz