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