この記事の目的
しゃくとり法のバグりにくい実装の紹介です！
しゃくとり法(尺取り法)って？
しゃくとり法の説明自体は、とってもいいまとめがあるのでこちらをご覧ください。
しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ
でも、しゃくとり法ってバグりません？
しゃくとり法っていざ書いてみるとかなりの確率でバグります。
区間の端を表す添え字 $l$ と $r$ の動かし方が結構混乱します。
この記事ではdeque(両端キュー)を使った実装を紹介します。
なんとこの実装では添え字を使う必要がありません！
deque(両端キュー)によるしゃくとり法の実装
次の問題を例にとって説明します。
長さ $n$ の整数列 $A = \{a_1, a_2,..., a_n\}$の連続部分列で、その要素の積が $K$ 以下となるものの長さの最大値を求める問題です。
次のように、連続部分列をdequeで表現して実装します。
from collections import deque
## 入力の受け取り
n, k = map(int, input().split())
a = [int(input()) for i in range(n)]
## コーナーケースの処理
if 0 in a:
print(n)
exit()
ans = 0
q = deque()
p = 1 ## 今、見ている区間の要素の積をpで管理する。
for c in a:
q.append(c) ## dequeの"右端"に要素を一つ追加する。
p *= c
while q and p > k: ## 要素の積がKを超えているか？
rm = q.popleft() ## 条件を満たさないのでdequeの"左端"から要素を取り除く
p //= rm ## 取り除いた値に応じて要素の積を更新する
ans = max(ans, len(q)) ## dequeに入っている要素の積がK以下になるまで区間を縮めた。
print(ans)
はい！添え字が一切登場しませんね！
連続部分列をdequeの両端への追加と削除で管理しているので添え字が必要ありません。
右端への追加が区間を右に伸ばす事に相当し、条件を満たさないなら左端の要素を取り除いていく事によって区間の左を縮めています。
whileを抜けた時には条件を満たす最大の長さの連続部分列がdequeに入っている事になります。
printデバッグで確認すると分かりやすいでしょう。
N, K = 7 , 6
A = [4, 3, 1, 1, 2, 10, 2]
deque([4])
deque([3])
deque([3, 1])
deque([3, 1, 1])
deque([3, 1, 1, 2])
deque([])
deque([2])
標準的な実装でありがちな、$l$ が $r$ を追い越してしまった！という事はdequeの要素の数が負になる事に相当するので起こりえません。
空の区間は条件を満たす事がほとんどなので、whileがbreakするからです。
稀に空の区間が条件を満たさない事もありますが、その場合は空のdequeからpopしようとする例外が発生します。
怖い時は while q and (条件) としておくとよいでしょう。
一般の場合
より一般的には下のようなコードになります。
q = deque()
for c in a:
q.append(c) ## dequeの右端に要素を一つ追加する。
(追加した要素に応じて何らかの処理を行う)
while not (満たすべき条件):
rm = q.popleft() ## 条件を満たさないのでdequeの左端から要素を取り除く
(取り除いた要素に応じて何らかの処理を行う)
(何らかの処理を行う。whileがbreakしたので、dequeに入っている連続部分列は条件を満たしている。特に右端の要素から左に延ばせる最大の長さになっている。)
あなたもdequeで快適なしゃくとりライフを！
追記
右から入れて左から出してるだけなので両端キューでなく、ただのキューで十分ですね。
$N$ 個の要素がキューに入って最大でも一回出るだけなので、キューに関する操作は最大でも $2N$ 回になります。
この事から計算量が $O(N)$ になる事も分かります。
ちなみにPythonではcollections.dequeが速いのでdequeを使っておけば問題ないでしょう。