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 <aaqui...@gmail.com <javascript:>
> > wrote:
>
>> http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/
>>
>>
>> On Tue, Sep 10, 2013 at 11:46 PM, kumar raja
>> <rajkuma...@gmail.com<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 algogeeks+...@googlegroups.com <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 algogeeks+...@googlegroups.com <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 algogeeks+unsubscr...@googlegroups.com.
