@atul.. thanks for pointing out.. i m doing a small mistake in
calculating closest element found... and i have rectified it below...
Also i have missed a corner case in the above solution hence i m
putting it down here...
3a) Corner case: Do modified binary search for closest element smaller
than equal to X in the array B[][0] .... If the index of the search
returned is 'j' then
closest to X = B[j][0]
subarray = A[ 0 ... B[j][1] ]
3) Now for each element B[i][0] , do a (modified) binary search for
the closest value smaller than equal to (X + B[i][0]) in array B[i
+1... n][0] ,
Say the found index after binary search is j ( which is > i)...
4) If B[i][1] < B[j][1] ( if not, then go to step 3), then keep track
of the max no. closest to X ( that is B[j][0] - B[i][0] )...
/*
In case you want to return the indices of the subarray for the max
closest element to X ,
then have two variable maxi and maxj such that
maxi = B[i][1]+1
maxj = B[j][1]
whenever you get a new max. no closest to X in step 4.
*/
--------------------------------------------------------------------------
Your example:
let X=12;
Corner case:
closest to X = 10 ... i=0, j = 3
Other cases:
12 + 2 = 12 , closest element found = 10 , closest to X = 10 - 2 =
8.... i = 1, j = 3
12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =
12 .... i = 2, j = 4
12 + 6 = 18 , closest element found = no element found
12 + 10 = 22 , closest element found = no element found
Hence the max closest to X is 12...and the sub array is A [ 2 .. 4 ]
On Dec 1, 10:21 am, atul anand <atul.87fri...@gmail.com> wrote:
> @sourabh :
>
> *Cumulative SUM*
>
> *i*
>
> 2
>
> 0
>
> 3
>
> 1
>
> 6
>
> 2
>
> 10
>
> 3
>
> 15
>
> 4
>
> above will the array B[][] formed for array A[]={ 2,1,3,4,5 }
>
> let X=12;
> 12 - 2 = 10 , closest element found = 10 , *closest to X = 2 + 10 =12*
> ,*i = 0 , j = 3
> * // this is the answer , so i am calculating other
>
> max number found closest to X=12 is 12
>
> to return sub-array for this max sum
>
> *i = 0 and j=3
>
> *hence from given A[]={ 2,1,3,4,5 } we will get sub-array = {2,1,3,4} ( sum
> = 2 + 1 + 3 + 4 = 10 )
>
> sub-array should be from i = 2 to j = 4 which is {3,4,5} (sum = 3 + 4 + 5
> = 12)
--
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.
