Розв’яжемо задачу у зворотному порядку — додаватимемо вправи до програми. Нехай dp_i — довжина максимальної послідовності вправ, що задовольняє умови, якщо -та вправа виконується останньою.
Для кожної довжини зберігатимемо у pos_x всі позиції , де dp_j = x.
Коли додаємо вправу :
Знаходимо dp_i, перебираючи від до a_i - 1. У pos_x шукаємо найправішу позицію j < i, де dp_j = x. Перевірим, чи a_j < a_i, якщо це так, то оновимо dp_i = \max(dp_i, x + 1).
Після цього оновлюємо вправи, для яких -та може бути передостанньою. Будемо пробувати шукати позиції які треба оновити. Серед позицій , де dp_k = dp_i, знайдемо найлівішу для якої виконується i < k. Якщо виконується a_i < a_k, то оновимо значення dp_k і продовжимо шукати позиції . Після цього рекурсивно повторюємо процес для наступних вправ .