Re: [algogeeks] Find the max element of sets of size K
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:
pairint, 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.comjavascript:
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.
Re: [algogeeks] Find the max element of sets of size K
question is different...here we have to find max of k elements in the
window..not max subarry of size kfoe eg input is say ... 1 4 5 66 7 9
and k=3
then output should be
(1,4,5) = 5
(4,5,66) = 66
(5,66,7)=66
(66,7,9)=66
output - 5,66,66,66
On 19 Sep 2013 19:00, igor.b...@gmail.com igor.b...@gmail.com wrote:
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:
pairint, 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 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
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.
--
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.
--
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.
--
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.
Re: [algogeeks] Find the max element of sets of size K
@kumar raja : check the last approach in given link. On Wed, Sep 11, 2013 at 4:44 PM, kumar raja rajkumar.cs...@gmail.comwrote: 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 aaquib8...@gmail.com wrote: http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/ On Tue, Sep 10, 2013 at 11:46 PM, kumar raja rajkumar.cs...@gmail.comwrote: 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+unsubscr...@googlegroups.com. -- 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+unsubscr...@googlegroups.com. -- 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. -- Regards, Sourabh Kumar Jain +91-8971547841 -- 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.
Re: [algogeeks] Find the max element of sets of size K
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 aaquib8...@gmail.com wrote: http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/ On Tue, Sep 10, 2013 at 11:46 PM, kumar raja rajkumar.cs...@gmail.comwrote: 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+unsubscr...@googlegroups.com. -- 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+unsubscr...@googlegroups.com. -- 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.
[algogeeks] Find the max element of sets of size K
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+unsubscr...@googlegroups.com.
Re: [algogeeks] Find the max element of sets of size K
http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/ On Tue, Sep 10, 2013 at 11:46 PM, kumar raja rajkumar.cs...@gmail.comwrote: 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+unsubscr...@googlegroups.com. -- 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+unsubscr...@googlegroups.com.
