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:
- 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).
- Now we have the index of the first integer that's at least 2. Mark it as the leftmost point of our candidate sequence.
- 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.
- 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.