Find the maximum sum of all contiguous subarrays and not consecutive each others which its length at most 'k' in a given array

Question

Problem: Given an array 'arr' and an integer 'k', find the maximum sum of all subarrays of 'arr' whose size is at most 'k'. Note that you can't choose subarrays which are consecutive or overlap each other.

Constraints: 0 <= arr.size() <= 10^5; 0 <= arr[i] <= 10^5; 1 <= k <= 10^5;

For example:

1. arr = [1, 10, 7, 3, 4] and k = 1. The answer will be 14. Explanation: We can only choose subarrays of 1 size, so we will choose [10] and [4], sum of them is 14. You can't choose [10],[7],[4] because [10] and [7] are consecutive subarrays.
2. arr = [15 9 11 11 1 12 18 18 18 8 1] and k = 3. The answer should be 94 Explanation: Subarrays are [15], [11, 11], [12, 18], [18, 8, 1], These sums are 94.

This is an update of the House Robber problem and can be easily solved using dynamic programming:

dp[i] = max(dp[i-2] + arr[i], dp[i-1])

I can solve this problem by adding one more dimension into the dynamic array:

dp[i][j] = max(dp[i-2][j-1] + arr[i], dp[i-1][k])

But the problem is that above solution will exceed the time limit for worst case scenario: k = 10^5 and arr.size() = 10^5. It also runs very slow even when k = 10^4 and arr.size() = 10^4 because the time complexity is O(n*k).

I have tried to remove the smallest value from a subarray starting with arr[0:k+1], and then continue to remove in arr(j+1:j+k+1) (j is the index of removed value) but it goes wrong somewhere.

Is there any way to reduce the time complexity for this solution?

Thank you for spending your time.

Answer 1

Add the dimension, then use the idea of an optimal fringe.

First, as @Neil suggested, it is easier to minimize the holes. Each hole must be within k+1 of the previous one. We will do that by keeping an array best_holes of pairs (index of last hole, sum of holes). It starts with a fake element (-1, 0) representing a hole before the start of the array.

We don't need to keep track of the possibility of keeping a hole if we can do as well or better by placing a later one.

We also drop best holes when they are too much earlier to not have another hole after them.

Here is O(n) code.

from collections import deque

def best_sum (ary, k):
    best_holes = deque([(-1, 0)])
    for i in range(len(ary)):
        # Value of a hole at i plus the best best hole.
        value = ary[i] + best_holes[0][1]

        # Get rid of best_holes that this is better than.
        while value <= best_holes[-1][1]:
            best_holes.pop()

        # Record this best hole.
        best_holes.append((i, value))

        # Get rid of the best hole if it is too old to be used directly.
        if k < i - best_holes[0][0]:
            best_holes.popleft()

    return sum(ary) - best_holes[0][1]

print(best_sum([1, 10, 7, 3, 4], 1))
print(best_sum([15, 9, 11, 11, 1, 12, 18, 18, 18, 8, 1], 3))

If you want to know which arrays made up the sum, just use the following linked list trick:

def best_arrays (ary, k):
    best_holes = deque([(-1, 0, None)])
    for i in range(len(ary)):
        # Value of a hole at i plus the best best hole.
        value = ary[i] + best_holes[0][1]

        # Get rid of best_holes that this is better than.
        while value <= best_holes[-1][1]:
            best_holes.pop()

        # Record this best hole.
        best_holes.append((i, value, best_holes[0]))

        # Get rid of the best hole if it is too old to be used directly.
        if k < i - best_holes[0][0]:
            best_holes.popleft()

    answer = []
    i = len(ary)
    best_hole = best_holes[0]
    while -1 < i:
        if best_hole[0] + 1 < i:
            answer.append(ary[best_hole[0]+1 : i])
        i = best_hole[0]
        best_hole = best_hole[2]
    return list(reversed(answer))