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