Wyrażenie arytmetyczne w O(n lg n)
W etapie szkolnym XXXIII Olimpiady Informatycznej pojawiło się zadanie Wyrażenie Arytmetyczne. Zadanie to można było rozwiązać programowaniem dynamicznym w czasie O(n2). Zadanie to nie sprawiło zawodnikom wielu trudności. Mało kto jednak wie, że zadanie to można rozwiązać w czasie O(n lg n). Prezentuje to poniższy kod: