# Longest range with sum smaller than K [duplicate]

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

• 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 ... – Vor Oct 14 '12 at 23:52
• @Vor This is a simpler version of my answer in the linked question. Could you add it there as an alternative answer? – Yuval Filmus Oct 15 '12 at 0:54
• @YuvalFilmus: ok, I added the answer to that question; do you think I should add it here, too? – Vor Oct 15 '12 at 7:27