Hi Guys ,
I have coded the first part soon i will come with the
solution of part 2 :---
Let me know if u find any error case (hope u will find none)
public class Largestsubmatrix {
public point [][] a;
int [][] binmatrix;
public point loc;
public Largestsubmatrix(int [][] a) {
this.binmatrix =a;
}
public void preProcess(){
a = new point[binmatrix.length][binmatrix[0].length];
if(binmatrix[0][0] ==1){
a[0][0]=new point(1,1);
}
else {
a[0][0]=new point(0,0);
}
for(int i=1;i<a.length;++i){
if(binmatrix[i][0] == 1)
a[i][0] = new point(a[i-1][0].x +1 , 1);
else
a[i][0] = new point(0,0) ;
}
for(int i=1;i<a[0].length;++i){
if(binmatrix[0][i]==1)
a[0][i] = new point(a[0][i-1].y+1,1);
else
a[0][i]= new point(0,0);
}
int tempx , tempy;
for(int i=1;i<a.length;++i)
for(int j=1; j<a[0].length;++j){
if(binmatrix[i][j] == 1)
{
if(binmatrix[i-1][j-1] ==0)
{
if(a[i-1][j].x > a[i][j-1].y ){
a[i][j] = new point(a[i-1][j].x +1 ,1);
}
else{
a[i][j] = new point(1,a[i][j-1].y + 1);
}
}
else{
if(a[i-1][j].x > a[i][j-1].x)
tempx = a[i][j-1].x+1;
else
tempx = a[i-1][j].x+1;
if(a[i-1][j].y > a[i][j-1].y)
tempy = a[i][j-1].y+1;
else
tempy = a[i-1][j].y+1;
a[i][j] = new point(tempx,tempy);
}
}
else{
a[i][j] =new point(0, 0);
}
}
int val =-5;
loc = new point(0,0);
for(int i =0; i<a.length;++i)
for(int j=0; j<a[0].length;++j){
int temp = a[i][j].x * a[i][j].y;
val = (val > temp ? val : (temp)) ;
if(temp == val){
loc.x=i;loc.y=j;
}
}
}
public class point{
public int x;
public int y;
public point(int x, int y){
this.x=x;
this.y=y;
}
}
public static void main(String args[]){
int[][] a =
{{0,0,0,1,0,0,0},{0,1,1,0,0,0,0},{0,0,0,1,1,1,0},{0,0,1,1,1,1,1},{1,1,0,1,0,0,0},{1,1,1,1,0,0,0}};
Largestsubmatrix ls = new Largestsubmatrix(a);
ls.preProcess();
int size = ls.a[ls.loc.x][ls.loc.y].x * ls.a[ls.loc.x][ls.loc.y].y ;
System.out.print("point at (" + ls.loc.x + "," + ls.loc.y + " )" +
"size is " + size );
}
}
On Sun, Dec 26, 2010 at 3:31 AM, yq Zhang <zhangyunq...@gmail.com> wrote:
> How to solve the second question? it is different from the other question
> posted where it requres only SQUARE sub matrix.
>
> Sent from Nexus one
> On Dec 25, 2010 11:00 AM, "juver++" <avpostni...@gmail.com> wrote:
> > Try to search the answer before sumbitting the question here.
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> > For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
> >
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
