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