@ankit...
I don't think the algorithm is correct...
The check "max_ending_here < 0 && max_limit_here <=k" doesn't look
correct...
Also I am not able to figure out the importance of 0 in the check ..
Ankit, may be I am wrong. Hence, can you come up with the algorithm
explaining ( with a set of steps ) what you are doing here...
On Dec 1, 11:12 pm, atul anand <atul.87fri...@gmail.com> wrote:
> @ankit : sorry dude , its not working for given input
>
> {2,1,3,4,5} k=12,
> ans=12, sub-array={3,4,5}
>
> your algo will give ans=10 sub-array{0 to 3}
>
>
>
>
>
>
>
> On Thu, Dec 1, 2011 at 11:33 PM, Ankit Sinha <akki12...@gmail.com> wrote:
> > A little variation of kadane's algo will do as written below: -
>
> > #include "stdafx.h"
> > #include "stdlib.h"
>
> > int _tmain(int argc, _TCHAR* argv[])
> > {
> > int a[5] = {-1,3,1,2,-3};
> > int max_so_far= 0, max_ending_here= 0,max_limit_here=0,startIndex=0
> > ,
> > endIndex = 0, itr = 0;
> > int k=12;
> > for (itr = 0; itr<5;itr++)
> > {
> > max_ending_here +=a[itr];
> > if (max_ending_here < 0 && max_limit_here <=k)
> > {
> > max_ending_here = 0;
> > startIndex++;
> > }
> > else if (max_so_far <max_ending_here)
> > {
> > if (max_ending_here <= k)
> > {
> > max_so_far = max_ending_here;
> > endIndex = itr;
> > }
> > else
> > {
> > max_limit_here = max_ending_here;
> > max_ending_here = 0;
>
> > }
> > }
>
> > }
>
> > printf("%d%d%d", max_so_far, startIndex, endIndex);
> > system("PAUSE");
> > return 0;
> > }
> > Complexity O(n)
>
> > Cheers,
> > Ankit Sinha
> > On Thu, Dec 1, 2011 at 4:58 PM, sourabh <sourabhd2...@gmail.com> wrote:
> > > @atul...
> > > thanks dude for ur thorough screening of the algo and pointing out the
> > > mistakes... I think that's y its always said that until and unless we
> > > don't turn an algo to a working code we are never really sure whether
> > > its perfect and covers all the cases.
>
> > > On Dec 1, 4:23 pm, atul anand <atul.87fri...@gmail.com> wrote:
> > >> yup i made some calculation error....
>
> > >> Now this algo works perfectly :) :)
>
> > >> Thanks for your help and explanation :) :)
>
> > >> On Thu, Dec 1, 2011 at 4:26 PM, sourabh <sourabhd2...@gmail.com> wrote:
> > >> > @atul ...
>
> > >> > Reply 1:
> > >> > Yes, you are correct.. i missed it... Correct statement is as follows:
>
> > >> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =9 ,
> > >> > i = 3, j = 4
> > >> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
> > >> > =5 , i = 4, j = 4
>
> > >> > -------------------------------------------------------------
>
> > >> > Reply 2:
> > >> > I might be wrong in calculating 12 + 2 = 14.... but i guess you are
> > >> > not getting my point .... even if 14 is the search element, still the
> > >> > element smaller than equal to 14 in array B is 10 and not 15...
>
> > >> > Hence, the above calculation that you have made are incorrect.
>
> > >> > If you look at the problem statement it says that we have to find the
> > >> > sum which is smaller than equal to X.
> > >> > Now, if you look ta ur calculations you will see that your 'closest to
> > >> > X' search space contains elements 13 which is invalid as it is greater
> > >> > than 12...
>
> > >> > Hence, i m re-calculating the values based on the above given
> > >> > algorithm...
>
> > >> > 12 + 2 = 14, 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 = 15 , closest to X = 15 - 6 =
> > >> > 9 , i = 3 , j = 4
>
> > >> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 =
> > >> > 5 , i = 4 , j = 4
>
> > >> > Also, as calculated in the previous post the corner case gives 10 as
> > >> > the closest to X.
>
> > >> > Hence, max of all closest values to X = max { 8, 12, 9, 5, 10 } =
> > >> > 12.
>
> > >> > On Dec 1, 2:52 pm, atul anand <atul.87fri...@gmail.com> wrote:
> > >> > > and you made mistake above in calculating 12 + 2 = *12* , its 14
>
> > >> > > 12 + 2 = 14, closest element found = 15 , closest to X = 15 - 2 =
> > 13 ,
> > >> > i
> > >> > > = 1, j = 4
> > >> > > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3
> > =12 ,
> > >> > i
> > >> > > = 2, j = 4
> > >> > > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =
> > 11
> > >> > , i
> > >> > > = 3 , j = 4
> > >> > > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
> > = 5 ,
> > >> > i
> > >> > > = 4 , j = 4
>
> > >> > > out of {10,13,12,11,5 } , element 12 is closest to X ( which is
> > 12) .
> > >> > > So basically among this we have to find element closest X ( where
> > >> > element <
> > >> > > = X )
> > >> > > hence 12 is the answer.
>
> > >> > > On Thu, Dec 1, 2011 at 3:11 PM, atul anand <atul.87fri...@gmail.com
>
> > >> > wrote:
> > >> > > > @sourabh
>
> > >> > > > i guess you need to modify this statement :-
>
> > >> > > > 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)...
>
> > >> > > > 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 ??? how *
>
> > >> > > > *Cumulative SUM*
>
> > >> > > > *i*
>
> > >> > > > 2
>
> > >> > > > 0
>
> > >> > > > 3
>
> > >> > > > 1
>
> > >> > > > 6
>
> > >> > > > 2
>
> > >> > > > 10
>
> > >> > > > 3
>
> > >> > > > *15*
>
> > >> > > > 4
>
> > >> > > > for 12 + 6 =18 , closest element less than equal to 18 = 15 (15 <
> > 18 )
> > >> > > > ..right ??
>
> > >> > --
> > >> > 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.
