C# Advanced Topics - Problem 5. * Longest Non-Decreasing Subsequence
|
Input |
Output |
|
1 |
1 |
|
7 3 5 8 -1 6 7 |
3 5 6 7 |
|
1 1 1 2 2 2 |
1 1 1 |
|
1 1 1 3 3 3 2 2 2 2 |
2 2 2 2 |
|
11 12 13 3 14 4 15 5 6 7 8 7 16 9 8 |
3 4 5 6 7 8 9 |
Има допусната грешка в примерните изходи или е изпуснато нещо в условието.
Ще започна с най-вероятното място на грешката - условието на задачата,
Никъде в условието не е казано, че монотоността на нарастване в цялата подверига трябва да се запазва.
тогава вече това е пропуск в условието и отговорите ще са верни.
Защото в примерния изход за вход 1 1 1 2 2 2 верния отговор би трябвало да е 1 1 1 2 2 2 а не 1 1 1, защото 1 1 1 2 2 2 е ненамаляваща поредица и е с дъжина 6 т.е. по-голяма от дължина 3 на 1 1 1...
също и отговора на 1 1 1 3 3 3 2 2 2 2 трябва да е 1 1 1 2 2 2 2 защото това е ненамаляваща с дължина 7 по-голяма от дължина 4 на 2 2 2 2
I na men ne mi se poluchava neshto tazi zadacha samo tq mi ostana ot vsichki 14 ..
Относно тази задача, макар и със сгрешено условие някой да я е решил, че аз решенията които намирам във форума са с рекурсии и с проверка на всички възможни комбинации на всички възможни поредици,