wish_me's blog

By wish_me, history, 7 years ago, In English

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
  • Vote: I like it
  • -13
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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:

  1. (7) + Maximum of [3, 9, 10, 3]

  2. (6) + Maximum of [9, 10, 3]

  3. (3) + Maximum of [10, 3]

  4. (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!

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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].

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ^_^