De ce contează?
Vrei să afli câți oameni participă, în total, la toate grupurile dintr-o tabără. Ai putea lua fiecare grup, să numeri câți oameni are și să aduni — dar grupurile sunt foarte multe, mult mai multe decât oamenii. Întoarce întrebarea: mergi la fiecare OM și întreabă-l „în câte grupuri ești?". Aduni acele numere și ai exact același total, calculat mult mai ușor. Aceasta este toată ideea: nu mai numeri pe grup, ci pe om — schimbi obiectul peste care faci suma.
Tiparul
Multe probleme cer o sumă peste TOATE subsecvențele unui șir: „adună sumele tuturor subsecvențelor", „adună maximele lor", și așa mai departe. O subsecvență înseamnă aici o porțiune de poziții consecutive: pentru șirul de mai jos, subsecvențele sunt bucățile continue care încep la o poziție și se termină la alta.
Reflexul greșit e să le generezi pe toate și să aduni. Numărul lor crește cam ca pătratul lungimii, deci la șiruri mari devine imposibil. Tiparul corect: schimbi perspectiva — în loc de „cât aduce fiecare subsecvență", întrebi „cât aduce fiecare element la total". Suma rămâne aceeași, dar acum o calculezi element cu element, liniar.
Ti se cere suma valorilor a[i] peste toate subsecventele unui sir de N numere. Pentru fiecare subsecventa aduni elementele ei, apoi aduni toate aceste sume. N poate fi foarte mare, deci nu poti genera fiecare subsecventa. Ce tipar folosesti?
Oprește-te. Care e observația care face naivul să devină rapid? Formuleaz-o în gând, apoi verifică.