Given a matrix of positive and negative integers, Write a code which find out the sub-matrix with the largest sum.
eg.
0 2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
max sum is : 17
0 2
9 2
-4 1
-1 8
SOLUTION
Thanks to anonymous. My code writing effort got saved coz of him.
int main( void )
{
int N;
int t = 0;
int a[100][100];
int pr[100];
int S = -INF, 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++)
input 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 = -INF;
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 less than 0 )
{
t = 0;
j = i + 1;
}
}
if( s greater than S)
{
S = s;
x1 = x;
y1 = k;
x2 = z;
y2 = l;
}
}
}
print x1 y1 x2 y2
print S;
return 0;
}
Subscribe to:
Post Comments (Atom)
7 comments:
This can be solved easily by Kadane's algorithm in 2 dimension.
The code goes like this.
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;
}
@above:
correct
now find the maximum sub matrix having all ones in a 0-1 matrix, i.e. the area should be maximum.
welcome buddy
so any solution to my o-1 problem??
u can of course spent time on that :P
A small modification in Kadane's algorithm in 2 dimension will do.
Also, this 0-1 could be solved in n^2 time.
I'll post code after sometime.
hmm i am looking for n^2 approach
Post a Comment