区間の長さ 1 (paizaランク C 相当)

以下の 10 個の整数からなる数列が与えられます。

1 5 9 1 20 5 3 6 5 4

この数列において、総和が 15 以下の区間のうち、最大の長さを求めてください。

---

(ヒント)

最大の長さを知りたい場合も、区間を数え上げるときと同様の考え方でしゃくとり法をおこなうことができます。

区間が [left, right) のとき、right を進められるところまで進めた後、区間を数えたい場合は

(区間の左端を left に固定したときの [left, right) 内の条件を満たす区間の数) = right - left

とすることで、求めることができました。

この right - left について考えると、左端を left に固定したときの最右の右端 right が求まっているため、最大の区間の長さとしても用いることができるとわかります。

例えば、区間が[2, 5) の場合、right - left = 3 となり、その区間の長さと一致していることがわかります。

このことから、最大の長さを求めたい場合は

right を進められるところまで進める
これまでの最大の長さと right - left を比べて、大きい方を最大の長さとして更新する

という動作を繰り返すことで求めることができます。

これらのヒントを元に、この問題を解いてみましょう。