@ Gaurav
I don't think the above nlogn approach will work. If i m not wrong,
the above nlogn approach is a modification of the nlogn algo for
maximum continuous subset problem.
I have a doubt with the crossing subarray solution. I see that your if
and while loop breaks out if "totalsum <=K" is not satisfied. But, its
very much possible that once part of the array is exhausted and the
other half is still left, the moment the "totalsum > = K" you are
breaking out which is not correct as there may be negative elements
after the sum crossed K which will result in the max closest and <=K.
Also, imagine in the first if loop it hits else "break" part wherein
both subarrays (lo, mid) and (mid +1, high) are not yet exhausted and
sum is greater then K and as a result of which it will break out of
the while loop since the next 2 elseifs will fail.
Gaurav, i may be wrong, but then if you could explain/validate the
above algo as in on what criteria you are sure that the above checks
will work it would be easier to understand the issues that currently i
feel are there..
On Dec 11, 1:41 am, Gaurav Kumar <gkuma...@gmail.com> wrote:
> Here is the code for O (nlgn) time complexity using recursion written in Java:
>
> public class SubArray {
> static int A [] = {2, 1, 3, 4, 5};
> static int k;
>
> private class Result {
> int lo;
> int hi;
> int total;
>
> Result(int lo, int hi, int total) {
> this.lo = lo;
> this.hi = hi;
> this.total = total;
> }
> }
>
> public static void main(String args[]) {
> k = Integer.valueOf(args[0]);
> SubArray sub = new SubArray();
> Result result = sub.findSubarray(0, A.length-1, k);
> System.out.println("lo: " + result.lo + ", hi: " + result.hi
> + ", total: " + result.total);
> }
>
> / * this has O(n) */
> private Result findCrossingSubarray(int lo, int mid, int hi, int k) {
> System.out.println("Finding crossing subarray for lo: " + lo
> + ", mid " + mid + ", hi: " + hi);
> int totalsum = 0;
> int leftPosition = -1;
> int rightPosition = -1;
> int i = mid;
> int j = mid+1;
> while(i >= lo || j <= hi) {
> System.out.println("i = " + i + ", j = " + j + ",
> left = " +
> leftPosition + ", right = " + rightPosition + ",
> total = " + totalsum);
> if(i >= lo && j <= hi) {
> // perfect
> if(A[i] < A[j] && A[j] + totalsum <= k) {
> totalsum += A[j];
> rightPosition = j;
> j++;
> } else if(A[i] + totalsum <= k) {
> totalsum += A[i];
> leftPosition = i;
> i--;
> } else {
> break;
> }
> } else if(i < lo && j <= hi && A[j] + totalsum <= k) {
> totalsum += A[j];
> rightPosition = j;
> j++;
> } else if(i >= lo && j > hi && A[i] + totalsum <= k) {
> totalsum += A[i];
> leftPosition = i;
> i--;
> } else {
> break;
> }
> }
>
> System.out.println("Crossing subarray: " + leftPosition + "
> to " + rightPosition + ", sum = " + totalsum);
> return new Result(leftPosition, rightPosition, totalsum);
> }
>
> /* this has O(lgn) time complexity */
> private Result findSubarray(int lo, int hi, int k) {
> System.out.println("Finding subarray between " + lo + " and "
> + hi);
> if(lo == hi) return new Result(lo, hi, A[lo]);
>
> int mid = (lo + hi) / 2;
> System.out.println("Dividing A at " + mid);
> Result leftResult = findSubarray(lo, mid, k);
> Result rightResult = findSubarray(mid+1, hi, k);
> Result crossResult = findCrossingSubarray(lo, mid, hi, k);
>
> if( leftResult.total <= k &&
> leftResult.total >= rightResult.total &&
> leftResult.total >= crossResult.total)
> return leftResult;
> else if(rightResult.total <= k &&
> rightResult.total >= leftResult.total &&
> rightResult.total >= crossResult.total)
> return rightResult;
> else return crossResult;
> }
>
> }
>
> Gaurav
>
> On Dec 7, 2011, at 6:40 AM, sourabh singh wrote:
>
>
>
>
>
>
>
> > @ 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 <singhsourab...@gmail.com> 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 <hhy...@gmail.com> 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 <gigir...@gmail.com> 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 <singhsourab...@gmail.com> 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 <sourabhd2...@gmail.com> 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 <singhsourab...@gmail.com> 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 <sourabhd2...@gmail.com> 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 <singhsourab...@gmail.com>
> >>>>>>>> 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 <kumarmohit...@gmail.com> 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
> >>>>>>>>>> algogeeks@googlegroups.com.
> >>>>>>>>>> To unsubscribe from this group, send email to
> >>>>>>>>>> algogeeks+unsubscr...@googlegroups.com.
> >>>>>>>>>> For more options, visit this group at
>
> ...
>
> read more »
--
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.
