You are right the algorithm is based on the max subarray problem. The difference is the logic to get the crossingSubArray() method. The way it works is like this:
The outer while loop, makes sure that left position or right position at least one of this should be between lo and hi values otherwise we exit. To initialize we keep two values i and j to follow the indices in the left and right direction of the mid element. In this while loop, we try to find the best possible subarray from mid element and increasing the size either on the left side or on the right side, such that the sum is always <= k. Think of a rubber band, where you are trying to rope in elements from either side, provided they satisfy our sum <= k condition. There are 3 cases in the while clause, which are catered for the 3 conditions one may encounter: 1. If i >= lo and j <= hi, what this means is that keep increasing the value of i and j or in our rubber band analogy extend the rubber band to the next highest element, because we want to maximize the sum but making sure that it remains less than equal to k. There are 3 conditions in this first if block, the first one compares the current element at A[i] with A[j] and picks the element which is bigger, but making sure that the sum is still less than equal to k. If not, pick the other value. 2. Now, the second else statement considers the case, if i value goes below the lowest value for the given array (for this recursive call). If this happens, all we are left with is to increase j till it reaches hi or the sum reaches to k or less. 3. This is same as the second else, except that this checks it if j is > hi, if that happens, we only decrease the i till it reaches lo or if the sum reaches k. I tried it for couple of negative values and the algorithm seems to work. You can check yourself by changing the static array. Let me know if you have more questions. One thing to note is that it solves the problem of finding 'a' subarray and not 'the' subarray because there may be more than one subarrays with the maximum sum. If you come up with an input which gives incorrect result or if you see any bug in the logic, please let me know, I will be happy to go over it again. Thanks Gaurav On Dec 12, 2011, at 4:44 AM, Lucifer wrote: > @ 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 <[email protected]> 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 <[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 >> >> ... >> >> 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 [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.
