ウィンドウは、連続した項目の連なりです。すべてのウィンドウを最初から足し直す(O(n × k))代わりに、スライドさせてください:入る項目を足し、出る項目を引きます。
固定のウィンドウ:最初のウィンドウの合計、その後ステップごとにtotal += values[i] - values[i - k]です。
可変のウィンドウは、2つのポインターleftとrightを使います。rightを動かしてウィンドウを伸ばし、それがルールを破ったら(繰り返されたページ、k日を超える空きの日、予算を超える合計)、ルールがまた成り立つまでleftを動かして縮めます。進みながら最もよいウィンドウを追ってください。どちらのポインターも前にしか動かないので、全体はO(n)です。
よくある質問:最も忙しい7日間、ページを再訪しない最も長いセッション、売上の目標に達する最も短い日の連続です。端を確かめてください:データより長いウィンドウ、すべて等しい項目、空のリストです。