Помощ за логиката на рашаване на задача 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 |
Много ти благодаря за отговора! Още преди няколко дни разгледах какви ли не решения на задачата, но не можах много да ги схвана. Затова и писах тук. Към този момент успях да си изградя собствена логика, с която Джъдж ми дава 100/100, но 5-ти тест не ми е напълно верен и това ми избожда очите
Знам къде ми е грешката, но не знам как да я оправя, така че да не разваля цялото решение. Някой с желание и свободно време би ли ми разгледал кода - https://pastebin.com/35sbVjjJ, за да ми даде насоки дали изобщо логиката ми е ок? На когото не му е ясна, мога да му я обесня 