Sliding-window sum greater than N using as few numbers as possible

Question

I have a problem that I'm trying to solve as part of a larger algorithm I'm implementing, and I don't know if there's a standard, well-known technique for this or not. Without going into too many details of the larger algorithm, I've managed to boil my problem down to the following mathematical summary:

I have a list of N non-negative integers, where N is a power of 2. (In the current implementation of the larger algorithm, it's 32, but it could be as low as 4). All of the integers in this list are between 0 and N-1. The total sum of the list is known to be at least 2N. I want to find a consecutive sequence of integers from the list where:

A) The integers in the sequence add up to at least N (higher is acceptable),

B) The length of the sequence is small (see below), and

C) I don't spend more than O(N) time finding the length of the sequence.

"Small" here does not necessarily mean "as small as possible", but it should at least be a local optimum: e.g., removing either the first or last integer from the sequence would drop the total to below N. I don't mind if I haven't found a global optimum, as long as it's a decent local optimum. Making two or three passes through the list to find a pretty good local optimum could be worth the time, but it would be better if I only had to make a single pass, or even just a partial pass (greedily find a local optimum and then stop without looking further). And making N passes through the list (for an O(N^2) solution) would be a waste of time that could more profitably be spent on other parts of my larger algorithm.

One other detail: it's highly likely that many numbers in this list will be 0. Also, due to some of the details of the larger algorithm, the numbers N/2, (N/2)-1, N/4, and (N/4)-1 are quite a bit more likely to appear in the list than other numbers. (Of course, (N/4)-1 only appears in the cases where N > 4). It's possible that knowing this fact might help find a better solution, but I haven't yet found a good way to take advantage of this knowledge.

What I've come up with so far is a kind of sliding-window approach:

1. Starting at the left of the list, skip over any 0's or 1's since the 0's are not going to contribute anything to the solution, and the 1's won't contribute much. (The 1's are safe to skip over, because we know that the list sums to at least 2N. So even if there are N-1 1's in the list, the last item would have to be at least N+1 -- which is actually impossible given the constraints on the problem. So there could be no more than N-2 1's in the list, and the last two numbers add up to N+2 and are therefore a valid, and very short, solution).
2. Now we have the index of the first integer that's at least 2. Mark it as the leftmost point of our candidate sequence.
3. Start expanding the candidate sequence to the right, keeping a running total of the sequence length and the sum of the sequence. Once the sum is >= N, stop. We have a candidate sequence.
4. Now start looking at the leftmost item of the candidate sequence, and consider whether dropping it out of the sequence (essentially sliding the left edge of the window to the right, reducing its length by 1) would reduce the sequence's sum to < N or not. If the sum would still be >= N, go ahead and drop the leftmost integer from the candidate sequence, then repeat this step.

I'm pretty sure this gives me a local optimum, but I wonder if there's a way to improve it. Is there a well-known technique for solving this problem, and I'm reinventing the wheel through ignorance?

BTW, I just saw Find the minimum count of elements summing to a pre-defined sum in the "Similar Questions" links on the right. My problem is very similar to that one, but with one important difference. That problem wants the smallest contiguous sub-array that sums to exactly N, whereas I'm quite happy to have a solution that sums to more than N. (As it happens, in my algorithm having a solution that sums to exactly N would be mildly better, but finding a local optimum quickly far outweighs getting a sum of exactly N). Still, if one of the solutions to that question might be adaptable to my situation, I'd like to know about it.

Answer 1

Yes. There is a linear-time algorithm for this problem. The algorithm finds the globally optimal solution, not just a local optimum or an approximation. I will assume the problem statement is as follows:

Input: an array $A[1..N]$, an integer $K$ with $1 \le K \le N$
Goal: find a (contiguous) subarray of length $\le K$ whose sum is as large as possible

This can be solved in $O(N)$ time using a divide-and-conquer algorithm. In particular, we will split the array into two equal-sized pieces, $A[1..N/2]$ and $A[N/2+1..N]$. Then there are three cases for where the maximal subarray lives:

• It is a subarray of $A[1..N/2]$ (wholly to the left of the split point).

• It is a subarray of $A[N/2+1..N]$ (wholly to the right of the split point).

• It is a subarray of the form $A[i..j]$ where $i \le N/2 < j$ (it straddles the split point).

We'll check all three scenarios to find the best subarray of each form, and take the best of those three candidates. The first two cases can be checked recursively. I'll show how to check the third case in $O(K)$ time. As a result, we'll obtain a recursive algorithm whose running time is given by the recurrence relation

$$T(N) = 2 T(N/2) + O(K).$$

As long as $K = O(N / \log N)$, the solution to this recurrence relation is $T(N) = O(N)$. Since you said $K$ is small in your case, the condition will surely hold, so we obtain a linear-time algorithm for your problem.

---

So how do we check for the subarray with maximal sum that straddles the split point and has length $\le K$? First, as a preprocessing step, we compute the suffix sums $S[i] = A[N/2-i] + A[N/2-i+1] + \dots + A[N/2]$ for $i=1,\dots,K-1$. Second, as another preprocessing step, we'll compute the prefix sums $P[j] = A[N/2+1] + A[N/2+2] + \dots + A[N/2+j]$ for $j=1,\dots,K-1$. Each of those steps can be done in $O(K)$ time by a linear scan (moving leftward from the split point for $S$, and moving rightward from the split point for $P$).

Then, for each $\ell=1,2,\dots,K-1$, we compute $Q[\ell] = \max(P[1],\dots,P[\ell])$. This is the best sum achievable by using a subarray of length $\le \ell$ starting at $A[N/2+1]$. This too can be computed using a linear scan.

Finally, for each $i=1,\dots,K-1$, we compute $S[i] + Q[K-i]$; this tells us the best sum achievable by using a subarray of length $\le K$ starting at $A[N/2-i]$. We take the largest such value, and that is the maximum sum possible for a subarray of length $\le K$ that straddles the split point.

Each of these four steps runs in $O(K)$ time, so the total running time to compute the best subarray of the third kind is $O(K)$, as claimed above.