Hey, isn't it as simple as:
1. Start at sum of the first K elements.
2. Move the "window" of size K by one element to the right at each step.
Subtract the left, add the right => get the new sum. Keep the maximum.
This executes in O(n) steps, requires O(1) memory. The code in C++ seems to
be trivial:
pair<int, int> max_k(int a[], int n) {
int sum_k = accumulate(a, a+k, 0);
int max_sum = sum_k, max_id = 0;
for (int i = k; i < n; ++i) {
sum_k = sum_k - a[i - k] + a[i];
if (sum_k > max_sum) {
max_sum = sum_k;
max_id = i - k + 1;
}
}
return make_pair(max_id, max_sum);
}
... or do I miss something?
On Wednesday, September 11, 2013 7:14:24 AM UTC-4, kumar raja wrote:
>
> I heard there exists a O(n) algorithm in DP? Does anyone has the idea
> about it?
>
>
> On 11 September 2013 03:21, Aaquib Javed <[email protected] <javascript:>
> > wrote:
>
>> http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/
>>
>>
>> On Tue, Sep 10, 2013 at 11:46 PM, kumar raja
>> <[email protected]<javascript:>
>> > wrote:
>>
>>> suppose we have n numbers and k <=n.
>>>
>>> Then a1,a2... ak is one set.
>>>
>>> then a2,a3.... ak+1 is other set.
>>> ...
>>> so totally we can have n-k+1 sets.
>>>
>>> how to figure out the maximum elements of all these k size sets with
>>> least possible time complexity and space complexity?
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to [email protected] <javascript:>.
>>>
>>
>>
>>
>> --
>> Aaquib Javed
>> B.Tech. Final Year
>> Electronics & Comm Engineering
>> MNNIT Allahabad.
>> +91-8953519834
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected] <javascript:>.
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
