@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 <atul.87fri...@gmail.com> 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" <rahul23111...@gmail.com> 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
>> <singhsourab...@gmail.com>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 <singhsourab...@gmail.com
>>> > 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
>>>> <atul.87fri...@gmail.com>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 <
>>>>> singhsourab...@gmail.com> 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 <atul.87fri...@gmail.com
>>>>>> > 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 <
>>>>>>> rahul23111...@gmail.com> 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 algogeeks@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.
>>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> You received this message because you are subscribed to the Google
>>>>>>> Groups "Algorithm Geeks" group.
>>>>>>> To post to this group, send email to algogeeks@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.
>>>>>>>
>>>>>>
>>>>>> --
>>>>>> You received this message because you are subscribed to the Google
>>>>>> Groups "Algorithm Geeks" group.
>>>>>> To post to this group, send email to algogeeks@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.
>>>>>>
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@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.
>>>>>
>>>>
>>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@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.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@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.
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
