@ giridhar IS correction missed increment j in outer loop: sry :-)
assuming u wanted k=13 ( max sum <=13)
start : i,j points to 1st element
keep a track of sum between i to j
outer loop: till j<a.length
sum=sum+a[j]
increment j
inner loop till sum exceeds k.
increment i . sum=sum-a[i]
keep track of max sum so far in max.
end : max will have max sum < k.
values after each looping of outer loop:
i j sum max
0 0 0 0
0 1 2 2
0 2 9 9
0 3 12 12
2 4 7 12
2 5 12 12
4 6 13 13
On 12/7/11, sourabh singh <[email protected]> wrote:
> @ giridhar IS
>
> assuming u wanted k=13 ( max sum <=13)
>
> start : i,j points to 1st element
> keep a track of sum between i to j
>
> outer loop: till j<a.length
> sum=sum+a[j]
> inner loop till sum exceeds k.
> increment i . sum=sum-a[i]
> keep track of max sum so far in max.
> end : max will have max sum < k.
>
> values after each looping of outer loop:
>
> i j sum max
> 0 0 0 0
> 0 1 2 2
> 0 2 9 9
> 0 3 12 12
> 2 4 7 12
> 2 5 12 12
> 4 6 13 13
>
> On 12/7/11, Chunyuan Ge <[email protected]> wrote:
>> My implementation, can anyone offer my test cases that i can verify?
>>
>> struct Deal
>> {
>> unsigned int nStartIndex;
>> unsigned int nEndIndex;
>> unsigned int nSum;
>>
>> Deal()
>> {
>> nStartIndex = 0;
>> nEndIndex = 0;
>> nSum = 0;
>> }
>> };
>>
>> int findBestDeal( const std::vector<unsigned int>& iHotelPrices, unsigned
>> int iLotteryPrice, Deal& bestDeal)
>> {
>> /* for loop to find a. best solution in history
>> b. best solution end with j-1
>> */
>>
>> Deal bestPotential;
>>
>> for (unsigned int i=0; i<iHotelPrices.size(); i++)
>> {
>> unsigned int nTemp = bestPotential.nSum + iHotelPrices[i];
>>
>> if ( nTemp <= iLotteryPrice)
>> {
>> bestPotential.nSum = nTemp;
>> bestPotential.nEndIndex = i;
>> }
>> else
>> {
>> int nStepCount = 0;
>> unsigned int newTemp = nTemp;
>> do
>> {
>> newTemp -=
>> iHotelPrices[bestPotential.nStartIndex+nStepCount];
>> nStepCount ++;
>> }
>> while (newTemp > iLotteryPrice);
>>
>> // better solution
>> bestPotential.nSum = newTemp;
>> bestPotential.nEndIndex = i;
>> bestPotential.nStartIndex += nStepCount;
>> }
>>
>> if (bestPotential.nSum > bestDeal.nSum)
>> {
>> bestDeal = bestPotential;
>> }
>> }
>>
>> return 0;
>> }
>>
>>
>>
>> On Wed, Dec 7, 2011 at 4:58 AM, GIRIDHAR IS <[email protected]> wrote:
>>
>>> @sourabh
>>>
>>> can you explain me how it will work for this example????
>>> a[]={2,7,3,4,5,8,10}
>>>
>>>
>>> On Dec 7, 12:17 am, sourabh singh <[email protected]> wrote:
>>> > @ sourabh :-) yep, got your point... it wont work for all cases.
>>> > but
>>> > if we set initial max to a negative value . say max possible 64 bit
>>> > -ve number.then ?
>>> > point is though the code has limitations it will work fine mostly.
>>> >
>>> > On 12/5/11, sourabh <[email protected]> wrote:
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > > @sourabh singh..
>>> >
>>> > > Hey u don't need an example... I see a check "sum > max" in ur code
>>> > > to
>>> > > calculate the max value, ryt ? Now ur initial value of max is set to
>>> > > 1. That means ur always assuming that the value whose closest is to
>>> > > be
>>> > > found is >= 1 , which is incorrect. What do you think ?
>>> >
>>> > > On Dec 6, 12:24 am, sourabh singh <[email protected]> wrote:
>>> > >> @ sourabh tried some cases its working on -ve as well. pls post
>>> > >> some
>>> > >> case in which it might not work.
>>> >
>>> > >> On 12/5/11, sourabh <[email protected]> wrote:
>>> >
>>> > >> > @sourabh..
>>> >
>>> > >> > I don't think it will work for all the cases.. did u consider
>>> negative
>>> > >> > integers as well... what i can understand from the above code is
>>> that
>>> > >> > u have taken 2 pointers of which one points to the beginning of
>>> > >> > the
>>> > >> > subarray and other one at the end of the subarray and u r
>>> > >> > shifting
>>> the
>>> > >> > pointers based on the closest value.. this app is fine for non-
>>> > >> > negative integers but will fail when the given input contains
>>> > >> > both
>>> neg
>>> > >> > and pos integers...
>>> >
>>> > >> > On Dec 5, 4:25 pm, sourabh singh <[email protected]>
>>> > >> > wrote:
>>> > >> >> @ mohit my first post on here. this solution got ac in spoj
>>> >
>>> > >> >> main()
>>> > >> >> {
>>> > >> >> unsigned int n,m,sum,max,i,j;
>>> > >> >> sum=0;max=1;
>>> > >> >> n=in.ReadNextUInt();
>>> > >> >> m=in.ReadNextUInt();
>>> > >> >> unsigned int *a = new unsigned int[n];
>>> > >> >> unsigned int *p = a;
>>> > >> >> for (i=0; i < n; i++)
>>> > >> >> *(p++) = in.ReadNextUInt();
>>> > >> >> i=0;
>>> > >> >> j=0;
>>> > >> >> while(j<n)
>>> > >> >> {
>>> > >> >> sum+=a[j++];
>>> > >> >> while(sum>m)
>>> > >> >> {
>>> > >> >> sum-=a[i++];
>>> > >> >> }
>>> > >> >> if(sum>max)
>>> > >> >> max=sum;
>>> > >> >> }
>>> > >> >> out.WriteUInt(max,'\n');
>>> >
>>> > >> >> out.Flush();
>>> > >> >> return 0;
>>> >
>>> > >> >> }
>>> >
>>> > >> >> On 11/28/11, Mohit kumar lal <[email protected]> wrote:
>>> >
>>> > >> >> > Given a array of positive integers ,You have to find the
>>> > >> >> > largest
>>> sum
>>> > >> >> > possible from consecutive sub-array but sum should be less
>>> > >> >> > than
>>> or
>>> > >> >> > equal
>>> > >> >> > to
>>> > >> >> > K and also find that sub-array. Ex- array={2,1,3,4,5} k=12,
>>> > >> >> > ans->12, sub-array={3,4,5}
>>> >
>>> > >> >> > Firstly i tried with brute-force and then i also tried to
>>> > >> >> > solve
>>> it by
>>> > >> >> > DP
>>> > >> >> > but complexity were same ( O(n^2)) ....so plz try to provide a
>>> > >> >> > solution
>>> > >> >> > for
>>> > >> >> > O(nlgn) or O(n).
>>> >
>>> > >> >> > --
>>> > >> >> > Mohit kumar lal
>>> >
>>> > >> >> > IIIT ALLAHABAD
>>> >
>>> > >> >> > --
>>> > >> >> > 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.
>>>
>>> --
>>> 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.
