Given an array, we need to find two subarrays with a specific length K such that sum of these subarrays is maximum among
all possible choices of subarrays.
arr size <10^5
n<10^3
Examples:
Input : arr[] = [2, 5, 1, 2, 7, 3, 0]
K = 2
Output : 2 5
7 3
We can choose two arrays of maximum sum
as [2, 5] and [7, 3], the sum of these two
subarrays is maximum among all possible
choices of subarrays of length 2.
Input : arr[] = {10, 1, 3, 15, 30, 40, 4, 50, 2, 1}
K = 3
Output : 3 15 30
40 4 50
Good day to you,
not sure if I understood your problem correctly, but imho:
a) First step: calculate sum of each subarray of length "K" (you can use 2 pointers or prefix sum to obtain it in O(N)). There will be N-K+1 such subarrays.
b) Now you can use some RMQ (segment tree, fenwick tree, sparse table, monotone queue, sqrt decmposition or any good other idea) to answer following queries: For each index (obviously not those in the end) try: Actual_index_sum + maximum of indexes which are at least "K"(+/-) on the right of actual index. [take maximum of these]
So .. on your example (2, 5, 1, 2, 7, 3, 0) (K==2)
Step a: [7, 6, 3, 9, 10, 3]
Step b:
(7) + Maximum of [3, 9, 10, 3]
(6) + Maximum of [9, 10, 3]
(3) + Maximum of [10, 3]
(9) + Maximum of [3]
..END.. (since no more suffixes availible)
Hope it is at least a little bit understandable
With reasonable RMQ you will be able to find even indexes so you could do whatever you want with your result
Good Luck & Have Nice Day!
Is the linear solution incorrect? I made f[], where f[i] — maximum sum of subarray of length k for prefix of length i, f[i] = max(f[i — 1], sum(i — k + 1, i)). We can update answer when we are calculating f array: ans = max(ans, sum(i — k + 1, i) + f[i — k].
Good day to you
imho it shall be correct
As you can see it is not much different from mine approach (yet I've written more generaly "RMQ"). The solution with "monotone queue" is very similar to your approach (yet I must admit your solution is easier to understand :P ) [and also linear]
Have nice day ^_^