I think we can also solve this using divide and conquer:
The algorithm is based on the concept of diving the current array into two
parts and then considering if the solution exists, in the first part from lo to
mid and last part from mid+1 to high and the case in which the subarray crosses
the mid of the array.
// initial call
find-subarray(A, a.length, k)
find-crossing-subarray(A, lo, med, hi, k) {
total-sum = 0;
i = med;
j = med+1;
sum = 0;
sum = A[i] + A[j]
while(sum < k) {
if(a[i-1] >= a[j+1]) {
if(a[i-1] + sum < k) {
sum += a[++i];
} else if(a[j+1] + sum < k) {
sum += a[++j];
} else {
total-sum = sum;
break;
}
} else {
if(a[j+1] + sum < k) {
sum += a[++j];
} else if(a[i-1] + sum < k) {
sum += a[++i];
} else {
total-sum = sum;
break;
}
}
}
return i, j total-sum;
}
find-subarray(A, lo, hi, k) {
if(lo == hi) return (lo, hi, A[lo])
mid = (lo + hi) / 2
left-low, left-high, left-total = find-subarray(A, lo, k)
right-low, right-high, right-total = find-subarray(A, mid+1, k)
cross-low, cross-high, cross-total = find-crossing-subarray(A, lo, mid,
hi, k)
if(left-total < k && left-total >= right-total && left-total >=
cross-total) return left-low, left-high, left-total;
else if(right-total < k && right-total >= left-total && right-total >=
cross-total) return right-low, right-high, right-total;
else return cross-low, cross-high, cross-total;
}
This gives it a running time of O(nlgn)
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.
