@atul...
As usual an editing mistake :)
int X[2][N] -> int X[2][N+1];
---------------------------------
Regarding the new fixed code's explanation:
Basically as explained by praveen..
There are 2 things that need to be done to solve the problem:
1) Pick 2 nos and see if their abs diff is > K or not.. If yes,
consider it to be 0 otherwise 1.
2) find the max sub square filed with 1's...
Now max subsquare can be found by using the following recurrence..
Say the 2D array which actually stores the 0-1 mapping is R[i.j],
F[i,j] -> the maximum subsquare that ends at 'i' row and 'j' column...
Hence,
F[i, j] = (R[i,j] == 0 ? 0 : 1 + min( F[i-1, j], F[i-1, j-1], F[i,
j-1] ) );
Now u can see that to calculate the value of F[i,j] we need access to
the prev row 'i-1' as well...
Hence, to reduce from 2-D array to 1-D array we need to do the
following:
1) Have a 1-D prev array for row 'i-1'
2) Have a 2-D curr array for row 'i'.
3) Calculate F[i,j] , on the fly and store its value in curr[j] ...
4) Once, all F[i,j]'s are calculated for the 'i'th row, make curr as
prev array and make prev as the curr array for next round of
calculations...
The reason being that, for 'i+1' iteration,
prev should point to 'i' row which hold F[i], and
curr should point to 'i+1' row to hold the new F[i+1] values..For
this we can use the array prev from the previous iteration..
Basically in X[2][N+1],
X[0] is prev , and
X[1] is curr..
Once we finish the current iteration and start a new one we switch the
roles of X[0] and X[1], rather than copying the values from X[1] to
X[0]...
----------------------------------
Let me know if u have concerns...
----------------------------------
On Jan 5, 12:44 am, gaurav bansal <gbgaur...@gmail.com> wrote:
> @all
> sorry for my prev post.
>
> On Jan 5, 12:42 am, gaurav bansal <gbgaur...@gmail.com> wrote:
>
>
>
>
>
>
>
> > your algo wont work for a[]={8,11,2} with k=7.
> > acc to u,ans should be 3,but it is 2.
> > you are not considering the diff between max and min value
--
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.
