Loading...
Ludmil.D avatar Ludmil.D 41 Точки

[C# Basic] Advanced Problem 8.* Longest Non-Decreasing Sequence

Write a program that reads a sequence of integers and finds in it the longest non-decreasing subsequence. In other words, you should remove a minimal number of numbers from the starting sequence, so that the resulting sequence is non-decreasing. In case of several longest non-decreasing sequences, print the leftmost of them. The input and output should consist of a single line, holding integer numbers separated by a space.

Тестовете както следва по условие:

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

за тест имам забелечка би трябвало очаквания резултат да е  3 4 5 6 7 8 16

l 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 =>
има условие което не се споменава което се крие зад (non-decreasing subsequence) => под множеството е или нарастващо или равно, което очевидно отговаря на условието да е не намаляващо :)
 за да стане още по ясно си добавих допълнителен тест:

1 11 1 12 1 13 1 3 1 14 1 - > 1 1 1 1 1 1

http://pastebin.com/JgMdw9L2

п.с. не намерих решения на този порблем за това си позволявам да пусна отделна тема.
edit: допълнителни тестове 1 2 3 1 1 1 - > 1 1 1 1 (като - most left) && Longest 1 2 3 4 4 4 4 -> 1 2 3 4 (most left) && Longes по идея на dim4o

Тагове:
3
Programming Basics
ethanrox avatar ethanrox 6 Точки

По доста сходен начин мислех и аз, докато гледах условието на задачата, но реших, че за subsequence от равни елементи се броят само поредните.

Тоест от 1 1 1 2 2 2 1, моето решение ти дава 1 1 1, а не 1 1 1 1. А иначе, също смятам, че тряба на примера в задачата да връща 3 4 5 6 7 8 16. 

0
Ludmil.D avatar Ludmil.D 41 Точки

Решението ти определено е бързо и работи за нарастваща поредица но не хваща равните елементи моята зависва на 28-то число .. май няма пълно щастие

0
HPetrov avatar HPetrov 822 Точки

Искам да те попитам защо пускаш цикъла да върти от последната стойност на комбинациите надолу? Смисъл има ли конкретно някакво значение дали ще си върви от 1 до max или обратно? А това, че ти увисва на 27-28 числа е малко кофти, да. Но като се замислиш колко итерации са за 2^28+ степен... :D

0
Ludmil.D avatar Ludmil.D 41 Точки

Да правилно си забелязал започвам от последната комбинация = 2^(броя на турсените цифри). Комбинацията се представя като полученото число от горната формула (2^28 примерно) се преобразува до бинарно т.е. 11111.. и на всяка позиция за 1-цата взимам число от въведения списък 2^2 -> 111 oт  arr[]{1 2 1} като идеята беше първото намерено да е отговора
(ама се оказа че не работи точно така защото отговора може и да е в последната половина т.е. при 000111 последните 111-ци да съдържат отговора)
Не си пазя кода преди модификацията ;/ но на кратко при него 1,1,2,2, -> 1,1,2,2 беше верния отговор 

0
vladislav_hadzhiyski avatar vladislav_hadzhiyski 66 Точки

http://pastebin.com/RQEbLUMd Това е моето решение на задачката.

По отношение на тестовете редица като:

1 1 1 3 3 3 2 2 2 2 -> 2 2 2 2

Мисля че теста е сгрешен защото най- дългата ненамаляваща редица е 1 1 1 3 3 3.

1
Ludmil.D avatar Ludmil.D 41 Точки
теста не е сгрешен за съжаление просто има условие което явно не е упоменато а се досещаме по него от тестовете (моя си логика :j ), но четвъртия тест със сигурност е сгрешен :) тест 4: 11 12 13 3 14 4 15 5 6 7 8 7 16 9 8 - > 3 4 5 6 7 8 9(вместо 9трябва да е 16 )
0
dim4o avatar dim4o 288 Точки

Според мен допълнителното условие за равните елементи е сложено за да усложни леко задачката, за която иначе си има много приятен и кратък алгоритъм. Проблема, е че няма съответствие между условието и примирете, а решението почва да изглежда малко изкуствено (поне при мен :). Не става ясно  какъв е случая при 1 2 3 1 1 1. За мен е очевидно 1 1 1 1, но знае ли човек. За 1 2 3 4 4 4 4 също може да се зачудиш...

Ето това е решението, което отговаря на моето разбиране за условието.

Това е другото ми решение. На по-различен принцип е. По-бавно е и направено само за ненарастващи редици, т.е. както си е по условието, но не и по примерите.

 

1
Ludmil.D avatar Ludmil.D 41 Точки
1 2 3 1 1 1 - > 1 1 1 1 (като - most left) && Longest 1 2 3 4 4 4 4 -> 1 2 3 4 (most left) && Longest p.s. заслужава си *-та :D по моя схема де ;j иначе съм съгласен че си има елегантно решение при друго условие и зададени тестове :)
1
dim4o avatar dim4o 288 Точки

Да, заслужава си *. Даже може би ** даже. Другите ги реших от раз - само тази ме затрудни.

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.