Doubt In Farmer Frenzy problem

#1


I have approached the problem as :
For a particular (i,j) to be top left corner of largest rectangle in matrix ,
if a = f(i+1,j) , b = f(i,j+1) and c = f(i+1,j+1) ,
then f(i,j) = largest(a,b,c) + second_largest(a,b,c) - smallest(a,b,c) + 1
the smallest is subtracted to avoid overlapping of submatrices.
Can you please rectify the approach and tell me where i am making mistake .
Thanks

#2

your approach does seem fine to me.
to better understand the issue, try to dry run your algorithm in this counter case example:
5 5
0 0 0 1 1
0 0 1 1 1
1 1 1 1 1
0 1 1 1 1
0 0 0 1 1

right approach: one of the right approach is through the concept of histograms.
run a loop for each row, considering each row as base of histogram and at each iteration find out the max area rectangle in that histogram. ans is max of all.

thanks

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.