0
$\begingroup$

Possible Duplicate:
Dynamic programming table for finding similar substrings is too large

Say I have a sequence $S$ of 0s and 1s such as $S = [1, 0, 0, 1, 0, 1]$

How would I efficiently find a pair $(i, j)$ such that $j - i$ is maximum and $(\sum_{z=i}^j S_z ) \leq K$

UPDATE

The following algorithm solves the above problem in O(n).

def longest_range_min_sum(S, K):
    longest = 0
    i = 0
    running_sum = 0
    while i + longest < len(S):
        if S[i + longest] == 1:
            running_sum += 1
        if running_sum > K:
            if S[i] == 1:
                running_sum -= 1
            i += 1
        else:
            longest += 1
    return longest
$\endgroup$
  • $\begingroup$ A hint: start with i=0 and find the max $j$ for which $\sum_{z=0}^j S_z \leq K$, and set $maxlen=j$; then "shift" the interval $[i,i+maxlen]$ to the right ($i=1,2,...$); at each step check if maxlen can be increased ... $\endgroup$ – Vor Oct 14 '12 at 23:52
  • $\begingroup$ @Vor This is a simpler version of my answer in the linked question. Could you add it there as an alternative answer? $\endgroup$ – Yuval Filmus Oct 15 '12 at 0:54
  • $\begingroup$ @YuvalFilmus: ok, I added the answer to that question; do you think I should add it here, too? $\endgroup$ – Vor Oct 15 '12 at 7:27

Browse other questions tagged or ask your own question.