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