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.
