Блог пользователя wish_me

Автор wish_me, история, 7 лет назад, По-английски

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
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +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:

  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 лет назад, # ^ |
      Проголосовать: нравится +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].

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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