@ atul and saurabh
Here is my code of what m trying to implement .
here starting at bottom right corner we try to come up moving row by row .
in end b matrix contain's dimention of rectangle which can be formed
from Aij in Bij (width,height)
plz.. post what u make of it... can it be improved to work for all case's
??
#include<iostream>
#include<conio.h>
using namespace std;
main()
{ int width=0,height=1;
int a[6][6]={0,1,1,1,1,0,
0,0,0,1,1,0,
0,1,1,1,1,0,
0,1,1,0,0,0,
0,1,1,0,0,0,
0,0,0,0,0,0 };
int b[6][6][2]={0};
int i,j;
for(i=0;i<6;i++)
{ b[5][i][width]=1;
b[i][5][width]=1;
b[5][i][height]=1;
b[i][5][height]=1;
}
for(i=4;i>=0;i--)
{
for(j=4;j>=0;j--)
{
if(a[i][j]!=a[i+1][j] & a[i][j]!=a[i][j+1])
{
b[i][j][width]=1;
b[i][j][height]=1;
}
else if(a[i][j]==a[i][j+1] &
a[i][j]!=a[i+1][j])
{
b[i][j][width]=b[i][j+1][width]+1;
b[i][j][height]=1;
//printf("widht\n");
}
else if(a[i][j]==a[i+1][j] &
a[i][j]!=a[i][j+1])
{
b[i][j][width]=1;
b[i][j][height]=b[i+1][j][height]+1;
// printf("height\n");
}
else
{
b[i][j][width]=min(b[i+1][j][width],b[i][j+1][width]+1);
b[i][j][height]=min(b[i+1][j][height]+1,b[i][j+1][height]);
}
}
}
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
printf("%d,%d ",b[i][j][width],b[i][j][height]);
}
printf("\n");
}
getch();
}
On Wed, Mar 14, 2012 at 8:59 PM, atul anand <[email protected]> wrote:
> @Sourabh : here we are talking abt 2 different problems in this
> post..which are little bit similar.
>
> 1) original question says find max subset of matix contaning '1' and '0'
>
> we knw recurrence to solve this problem , as posted above.
>
> 2) now your question is to find max subset of matrix which contain +ve or
> -ve numbers , not necessarily only '1' or '0'
>
> so in my solution , you need to give some input to solve this problem ....
> and that input is say matrix m[][].
> if you check my solution then in just modifies input matrix to find
> solution , its space complexity is O(1).
>
>
>
> On Thu, Mar 15, 2012 at 12:26 AM, Sourabh Singh
> <[email protected]>wrote:
>
>> @atul
>>
>> 1) it won't work for large dimention's coz their is a limit to size of
>> array we can declare on stack.
>> ( which is typically 10^6 as far as i know :-) ).
>>
>> 2) the algo i m trying to find would work in linear time. while this one
>> is more then O(n^2)
>> fo rvery very large input this algo would be very very slow.. making
>> it impractial..
>>
>> ( it's like if u can find substring's in linear time then why use an
>> O(n^2) algo ;-) )
>>
>> NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit
>> short on time to check implemention of your algo right now )
>>
>>
>>
>> On Wed, Mar 14, 2012 at 9:07 AM, atul anand <[email protected]>wrote:
>>
>>> @rahul: i have alreday explained it in the provided link.
>>> @sourbh : why it would not work for large dimension
>>> On 14 Mar 2012 19:39, "rahul sharma" <[email protected]> wrote:
>>>
>>>> @atul..plz tell me an example for square matrix...actually i faced it
>>>> first tym...it executes...but explain plz..
>>>>
>>>> On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh <
>>>> [email protected]> wrote:
>>>>
>>>>> @atul
>>>>>
>>>>> Also the histogram algo and algo given by you can't work on very very
>>>>> big dimentions. say 10^5 x 10^5 matrix.
>>>>> but if we can find a DP then we just need to keep 2 row's at a time.
>>>>> :-)
>>>>>
>>>>>
>>>>>
>>>>> On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh <
>>>>> [email protected]> wrote:
>>>>>
>>>>>> @atul
>>>>>>
>>>>>> read it ..
>>>>>>
>>>>>> it's good but more or less like the histogram algo.. i wanted a DP.
>>>>>> approach..
>>>>>>
>>>>>> here is some of wat i heard from a senior in colg..
>>>>>>
>>>>>> 1. at every index we can keep 4 variable
>>>>>>
>>>>>> ht: height of max rectangle possible at index above current
>>>>>> wt width " " " " "
>>>>>> " "
>>>>>> hl:height of max rectangle possible at index left of current
>>>>>> wl: " " " " "
>>>>>> " "
>>>>>>
>>>>>>
>>>>>> now problem is which one to take for current... index
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Tue, Mar 13, 2012 at 10:52 AM, atul anand <[email protected]
>>>>>> > wrote:
>>>>>>
>>>>>>> @ Sourabh: check solution i have posted in below link
>>>>>>>
>>>>>>>
>>>>>>> http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=en&lnk=gst&q=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh <
>>>>>>> [email protected]> wrote:
>>>>>>>
>>>>>>>> @ ALL
>>>>>>>>
>>>>>>>> finding square matrix is quite a standard question and nw an easy
>>>>>>>> one as everyone knows the reccussence atul has given.
>>>>>>>> but i wanted to find max rectangle..
>>>>>>>>
>>>>>>>> i know there is a DP for it. in O(n^2). for nxn matrix..don't know
>>>>>>>> the whole approach .but here is what i remember..
>>>>>>>>
>>>>>>>> 1. aproach is simple to keep track of max rectangle which can be
>>>>>>>> formed from any point taking that point as top left corner of max
>>>>>>>> rectangle and
>>>>>>>> proceed further down .
>>>>>>>>
>>>>>>>> can someone suggest how can be proceed further..
>>>>>>>>
>>>>>>>>
>>>>>>>> [ NOTE: problem occurs mainly when their are more than one
>>>>>>>> rectangles which can be formed from same point ]
>>>>>>>>
>>>>>>>> plz.. don't suggest the histogram method it's just a dirty way of
>>>>>>>> avoiding to work on getting this DP right. :-)
>>>>>>>>
>>>>>>>>
>>>>>>>> On Mon, Mar 12, 2012 at 11:29 PM, atul anand <
>>>>>>>> [email protected]> wrote:
>>>>>>>>
>>>>>>>>> here is the recurrence for solving this
>>>>>>>>>
>>>>>>>>> R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
>>>>>>>>> R[i,,j-1] ) );
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma <
>>>>>>>>> [email protected]> wrote:
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> April 4, 2010
>>>>>>>>>>
>>>>>>>>>> Given a binary matrix, find out the maximum size square
>>>>>>>>>> sub-matrix with all 1s.
>>>>>>>>>>
>>>>>>>>>> For example, consider the below binary matrix.
>>>>>>>>>>
>>>>>>>>>> 0 1 1 0 1
>>>>>>>>>> 1 1 0 1 0
>>>>>>>>>> 0 1 1 1 0
>>>>>>>>>> 1 1 1 1 0
>>>>>>>>>> 1 1 1 1 1
>>>>>>>>>> 0 0 0 0 0
>>>>>>>>>>
>>>>>>>>>> The maximum square sub-matrix with all set bits is
>>>>>>>>>>
>>>>>>>>>> 1 1 1
>>>>>>>>>> 1 1 1
>>>>>>>>>> 1 1 1
>>>>>>>>>>
>>>>>>>>>> --
>>>>>>>>>> You received this message because you are subscribed to the
>>>>>>>>>> Google Groups "Algorithm Geeks" group.
>>>>>>>>>> To post to this group, send email to [email protected].
>>>>>>>>>> To unsubscribe from this group, send email to
>>>>>>>>>> [email protected].
>>>>>>>>>> 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 [email protected].
>>>>>>>>> To unsubscribe from this group, send email to
>>>>>>>>> [email protected].
>>>>>>>>> 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 [email protected].
>>>>>>>> To unsubscribe from this group, send email to
>>>>>>>> [email protected].
>>>>>>>> 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 [email protected].
>>>>>>> To unsubscribe from this group, send email to
>>>>>>> [email protected].
>>>>>>> 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 [email protected].
>>>>> To unsubscribe from this group, send email to
>>>>> [email protected].
>>>>> 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 [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> 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 [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
