Помощ за логиката на рашаване на задача 05. Longest Increasing Subsequence от Arrays - More Exercise

Здравейте, колеги,

Моля някой да ми даде насоки /НЕ решение!/ как да я реша тази задача! Моята логика е да се направят НАРАСТВАЩИ комбинации с всички числа. Примерно, за този вход - 1 2 5 3 5 2 4 1, нарастващите комбинации ще са: 1 2 5, 1 2 3 5, 1 2 3 4, 1 2 5, 1 2 4, 2 5, 2 3 5, 2 3 4, 2 5, 2 4, 3 5, 3 4 и 2 4, като ще се изпринти 1 2 3 5, защото е най-дългата и най-лява комбинация. Обаче, като тръгна да пиша кода, нещо се обърква :( Правилна ли ми е изобщо логиката? Отбелязвам, че съм до материала с масиви!

Условие:

5.Longest Increasing Subsequence (LIS)

Read a list of integers and find the longest increasing subsequence (LIS). If several such exist, print the leftmost.

Examples

Input	Output
1	1
7 3 5 8 -1 0 6 7	3 5 6 7
1 2 5 3 5 2 4 1	1 2 3 5
0 10 20 30 30 40 1 50 2 3 4 5 6	0 1 2 3 4 5 6
11 12 13 3 14 4 15 5 6 7 8 7 16 9 8	3 4 5 6 7 8 16
3 14 5 12 15 7 8 9 11 10 1	3 5 7 8 9 11