By Dhanadeepa_Red, history, 12 months ago, ,

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

•
• -13
•

 » 12 months ago, # |   +4 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 understandableWith reasonable RMQ you will be able to find even indexes so you could do whatever you want with your resultGood Luck & Have Nice Day!
•  » » 12 months ago, # ^ |   +5 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].
•  » » » 12 months ago, # ^ |   0 Good day to youimho it shall be correctAs 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 ^_^