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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]>
>> > 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 [email protected].
>> > To unsubscribe from this group, send email to
>> > [email protected].
>> > 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
