Často můžeme výpočet algoritmu urychlit tím, že nové hodnoty počítáme s pomocí předchozích hodnot. Sice tím zvýšíme paměťovou složitost, ale většinou ne přilíš výrazně.
Pár definic pro následující úlohy: Podposloupnost je posloupnost vytvořená výběrem některých prvků původní posloupnosti tak, že zachováme jejich pořadí. Spojitá podposloupnost je úsek přímo po sobě jdoucích prvků posloupnosti.
Definice: Hladká podposloupnost je taková spojitá podposloupnost, že každé dva prvky posloupnosti se liší nejvýš o 1, tj. v posloupnosti se vyskytují prvky nejvýše dvou hodnot.
Máme posloupnost přirozených čísel. Úkolem je najít délku libovolné její nejdelší hladké podposloupnosti.
Horší řešení běží v čase O(N^2), lepší v čase O(N).
Máme posloupnost celých čísel. Počítáme součet prvků jejích spojitých podposloupností. Úkolem je najít největší takový součet.
Triviální řešení běží v čase O(N^3), ne úplně dobré v čase O(N^2), dobré v čase O(N).
Výpočet rozložíme do několika fází.
Máme posloupnost např. přirozených čísel, kde hodnoty prvků se mohou opakovat. Nějaká hodnota (nebo i více hodnot) se bude vyskytovat v největším počtu prvků. Cílem je zjistit tento počet výskytů nejčastěji se objevující hodnoty. Hodnota samotná nás ovšem nezajímá. Posloupnost čísel je konečná a máme uloženou v poli.