RecycleBin

Cum gândim problema

Uită o clipă de ștergeri și întreabă-te: ce înseamnă costul unui șir? E suma maximă a unei subsecvențe contigue — exact ce calculează Kadane. Acum revino la ștergeri: răspunsul final e tot o subsecvență, dar a șirului de după ștergeri. O astfel de subsecvență „trăiește” într-o fereastră $[l, r]$ a șirului original, din care am scos câteva blocuri; suma ei e suma elementelor rămase în fereastră.

Deci nu trebuie să simulăm ștergeri pe tot șirul. E destul să alegem o fereastră și să tăiem din ea bucățile proaste — dar tăierile au o regulă: fiecare bloc are lungime putere de $2$ și lungimile sunt distincte. „Distincte” e cheia: înseamnă că folosesc fiecare putere ($1, 2, 4, \dots$) cel mult o dată.