Задача о наибольшей возрастающей подпоследовательности

Определение:

Наибольшая возрастающая подпоследовательность строки [math] x [/math] длины [math] n [/math] - это последовательность [math] x[i_1] \lt x[i_2] \lt \dots \lt x[i_k] [/math] символов строки [math] x [/math] таких, что <tex> i_1 < i_2 < \dots < i_k <\tex>