List and Matrices: Largest Increasing Subsequence - Неразбрано условие/пример.
Като ментор съм сигурен, че ще получа доста въпроси за последните задачи от тази лекция, затова предварително искам да изясня тази задача. Става въпрос за тази презентация: https://softuni.bg/downloads/svn/programming-basics/Jan-2016/Part-II-Programming-for-Beginners/3.%20Lists-and-Matrices.pptx
Относно задачата на слайд 34. Largest Increasing Subsequence
Условието и примера са следните:
Read a list of integers and find the longest increasing subsequence. If several such exist, print, the leftmost. Examples:
| Input | | | Output |
| 1 | | | 1 |
| 7 3 5 8 -1 6 7 | | | 3 5 6 7 |
| 1 2 3 3 4 5 | | | 1 2 3 |
| 1 2 3 3 4 5 5 6 7 8 | | | 5 6 7 8 |
| 11 12 13 3 14 4 15 5 6 7 8 7 16 9 8 | | | 3 4 5 6 7 8 9 |
Ако разбирам правилно условието, бих казал, че изхода трябва да е такъв:
| Input | | | Output |
| 1 | | | 1 |
| 7 3 5 8 -1 6 7 | | | 3 5 6 7 |
| 1 2 3 3 4 5 | | | 1 2 3 4 5 |
| 1 2 3 3 4 5 5 6 7 8 | | | 1 2 3 4 5 6 7 8 |
| 11 12 13 3 14 4 15 5 6 7 8 7 16 9 8 | | | 3 4 5 6 7 8 16 |
Търсим най-голямото нарастващо подмножество. Алгоритъма, който съм използвал преди, когато решавах подобна домашна, ми дава резултатите по-горе, които мисля, че са правилни за даденото условие. Разбира се, преправих го да намира най-дългото нарастващо подмножество, а не най-дългото ненамаляващо подмножество, както беше в моята домашна. Я кажете аз ли не разбирам правилно нещата, или примерите на слайда са сгрешени? Все пак мисля да докладвам за грешка в инстанцията на курса, и този доклад да не стане по моя грешка. :)
Edit: На последния пример трябва да е 3 4 5 6 7 8 16, а не 3 4 5 6 7 8 9 както писах първо.