Maximum consecutive subarray sum for a variable sliding window size

Question

The Problem:

Given an array of integers L find the largest sum of a consecutive subarray of size k or less.

Constraints:

• 2 <= len(L) <= 10000

• 3 <= k <= len(L)

• each element in the array will have an absolute value no more than 200

• there will be at least one positive integer in the array L

Samples:

L=[-200, 91, 82, 43], k=3, the result should be 216

L=[41, 90, -62, -16, 25, -61, -33, -32, -33], k=5, the result should be 131

The Implementation:

Initially, I started with brute-forcing the problem, probing all sizes of the sliding window starting from k to 1. This immediately got me into "time limit exceeded" situation.

The idea implemented below is based on picking out only positive integers initially. For every positive integer, we are looking if the following integers in a window are contributing to the current sum or not, cutting off situations when current sum drops below zero:

def maximum_consecutive_subarray(L, k):
    global_max = 0

    for index in range(len(L) - 1, -1, -1):
        if L[index] < 0:  # skipping all negative values
            continue

        sliding_index = index
        positive_count = positive_sum = 0

        while sliding_index >= 0 and positive_count < k:
            if L[sliding_index] >= 0:
                positive_count += 1
                positive_sum += L[sliding_index]

                global_max = max(global_max, positive_sum)
            else:
                negative_count = 1
                negative_sum = L[sliding_index]

                while sliding_index - 1 >= 0 > L[sliding_index - 1]:  # iterating over all consecutive negative values
                    negative_count += 1
                    negative_sum += L[sliding_index - 1]
                    sliding_index -= 1

                    if positive_count + negative_count == k:  # break if sliding window size limit reached
                        break

                if positive_sum + negative_sum > 0:  # if we still contribute to the maximum value
                    positive_count += negative_count
                    positive_sum += negative_sum
                else:
                    break  # exit this window if nothing was to contribute

            sliding_index -= 1

    return global_max

I would like to know if we can further improve the solution time complexity wise and would appreciate any other feedback.

Answer 1

While I'm not one who really promotes pasting solutions, a lot of the answers seem to be answering in a way that a C programmer would answer the question. This is more a problem that you would want to solve in a pipeline in python due to that being how python does things fast and keeps a majority of the operations in C. Look into David Beasley's work if you want to minimize the amount of code you have to write by making everything into pipelines and checkout the collections library to get to know the tools that make things like windowed operations easy and a lot faster in python.

from collections import deque
from itertools import chain

def window(iterable,size):
    ''' yields wondows of a given size '''
    d = deque(maxlen=size)
    # normalize iterable into a generator
    iterable = (i for i in iterable)
    # fill d until it only needs one more
    for i in iterable:
        d.append(i)
        if len(d) == size-1:
            break
    # yield the windows
    for i in iterable:
        d.append(i)
        yield d

def max_sequential_subarray_sum(iterable, max_size):
    ''' returns the max sum of sequential slices of an iterable '''
    g = chain(*(window(iterable,i) for i in range(2,max_size+1)))
    return max(sum(i) for i in g if all(
        a<b for a,b in window(i,2)
    ) or all(
        a>b for a,b in window(i,2)
    ))


L=[-200, 91, 82, 43] 
k=3
print(max_sequential_subarray_sum(L,k))

L=[41, 90, -62, -16, 25, -61, -33, -32, -33]
k=5
print(max_sequential_subarray_sum(L,k))

Answer 2

def maximum_consecutive_subarray(L, k):

• consecutive seems to be a bit redundant here. Isn't a subarray consecutive by definition?

• You should add a docstring. Without it, there's a lot about the function that is far from clear just by looking at its name and signature. For example:

  • Is the subarray itself returned, a pair of (start, stop) indices, a starting index and length of extent, ... ? Or is just the maximal sum returned.
  • What is L? I would guess it's a list, and probably corresponds to the "array" from which the "subarray" is presumably picked. This is the easy one, but should still be mentioned in the docstring.
  • What is k? Is it the size of a sliding window? If so, is it the exact size? Is it the minimum allowable size? The maximum allowable size? Or is it something else? Or maybe k is something completely different. k might indicate some minimum or maximum value where, if the minimum is not met (or the maximum exceeded), k would be returned instead.

    global_max = 0

I guess this is ok, since one of the constraints you gave is that there is at least one positive element. However, you might want to add a comment to make it clear that this initialization is dependent on that constraint. There are several reasons for this:

• It makes it clear why initialization to 0 is valid
• It serves as a reminder that this portion of the code might need to change if that constraint is changed or eliminated entirely.
• It serves as a reminder that we are making an assumption that could possibly be invalid in the future. I.e., by explicitly stating the constraint, we provide for the possibility of re-verifying that constraint still holds as part of some future code review.

    for index in range(len(L) - 1, -1, -1):

Why are you working back-to-front? Why not work font-to-back? Maybe there is a good reason, but it's not clear to me.

        if L[index] < 0:  # skipping all negative values
            continue

It's fairly obvious that you are skipping the negative values, even without the comment. What more important, though, is why? Shouldn't negative values be included in the sum? If yes, then why are they being skipped? If no, why not? The rationale is much more important here than the tactic used.

        sliding_index = index

It looks like you are keeping track of the other end of the subarray via sliding_index. There's nothing wrong with that. However, you could also use the current window size to derive sliding_index from index.

        positive_count = positive_sum = 0

        while sliding_index >= 0 and positive_count < k
            if L[sliding_index] >= 0:
                positive_count += 1
                positive_sum += L[sliding_index]

                global_max = max(global_max, positive_sum)
            else:
               negative_count = 1
               negative_sum = L[sliding_index]

               while sliding_index - 1 >= 0 > L[sliding_index - 1]:  # iterating over all consecutive negative values
                   negative_count += 1
                   negative_sum += L[sliding_index - 1]
                   sliding_index -= 1

                   if positive_count + negative_count == k:  # break if sliding window size limit reached
                       break

               if positive_sum + negative_sum > 0:  # if we still contribute to the maximum value
                   positive_count += negative_count
                   positive_sum += negative_sum
               else:
                   break  # exit this window if nothing was to contribute

I'm not sure if this is a botched attempt at pre-mature optimization, but this can be simplified a lot.

• There's no need to treat negative elements any different from positive elements.
• Track the window size with one variable, not two.
• Keep the sum in one variable, not two.

You can replace this entire section of the code with something much simpler. For example:

    window_sum = 0

    for sliding_index in L[index, max(0, index-k), -1]:
        window_sum += L[sliding_index]
        global_max = max(global_max, window_sum)

Answer 3

Maximum subarray is pretty well known problem with a simple algorithm to solve in O(n). Directly from the link above:

def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

The problem mentions at least one positive integer, so this is equivalent to the above:

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

This is pretty simple to extend to a maximum window size k:

def max_subarray(A, k):
    max_ending_here = max_so_far = window = 0
    for i, x in enumerate(A):
        if window == k:
            max_ending_here, window = max((last_x, 1), (max_ending_here-A[i-k], window-1))

        max_ending_here, window = max((x, 1), (max_ending_here+x, window+1))
        last_x, max_so_far = x, max(max_so_far, max_ending_here)
    return max_so_far

Example:

In []: max_subarray([41, 90, -62, -16, 25, -61, -33, -32, -33], 5)
Out[]: 131
In []: max_subarray([-200, 91, 82, 43], 3)
Out[]: 216

Answer 4

I have an \$O(n)\$ solution for the problem. You can slightly modify the Kadane's algorithm and implement here. Firstly the problem statement shouldn't state "consecutive subarray", that's the wrong definition as subarray will have consecutive elements.

I won't give you the code, just the algorithm. So lets start. Let's take the sample 1 as example:

L=[-200, 91, 82, 43], k=3

• Firstly initialize two variables max_till_here, max_so_far, count, max_so_far will store the answer, count will store window size.
• start with idx = 0, initially all variables are set to 0, now add L[idx] to max_till_here and check whether the value is negative , it is here so we will reset max_till_here to 0 and thats it.
• now idx becomes 1, max_so_far is still 0, again we add L[idx] to max_till_here and check if value is positive, since it is so we check if max_so_far is lesser than max_till_here, yes it is so max_so_far gets updated to 91, we also increment count as our current window size has become 1.
• now idx has become 2, we check if count > k, if it is then we subtract a[idx-k] from max_till_here
• now we add L[idx] to max_till_here and check for sign and repeat the same process, also remember if adding L[idx] makes value negative then we reset count = 0 and at each point we update our max_so_far if value is positive.
• we add L[2] to max_till_here and update max_so_far, then we add L[3] to max_till_here and update max_so_far. So, ultimately our max_so_far becomes 216 and voila!! here is your answer.