@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.