[C#] Arrays - 18 задача.


10

 

Условие на задачата:
* Write a program that reads an array of integers and removes from it a minimal number of elements in such way that the remaining array is sorted in increasing order. Print the remaining sorted array. Example:
 {6, 1, 4, 3, 0, 3, 6, 4, 5} -> {1, 3, 3, 4, 5}
 
Идея за решение:

I. Заделяме 2 масива с дължина равна на масива, който ще обхождаме:

1-ви масив ще съхванява всички дължини. С други думи всеки елемент от него ще съхранява текущата дължина на най-голяма подредица за него.
2-ри масив ще съхранява индекса на неговия поделемент.

II. Проверяваме всеки елемент с неговите предшественици, за да намерим какви числа са по-малки от него и кое от тях е с най-много предшественици.

III. Взимаме най-голямата дължина и съставяме нов масив, в които ще съхраним нашия резултат.

IV. Отпечатваме резултата.

Моето решение:
http://pastebin.com/McbFpvzb

EDIT:

Поправена и изправна по препоръките на колегата valentinvs.
 




Отговори



0

GitHub

Доста интересна задачка. Най-добрия отговор е когато махнем най-малко елементи. Почвам от едно и махам всеки елемент и проверявам дали масива е сортиран. После махам два елемента (и по точно всички възможни комбинации от два елемента) и пак проверявам .. така докато не се стигне до отговор. Първия достигнат ще е верният защото при него махаме най- малко елементи.


от dzhenko (3893 точки)


0

Ето едно кратко решение на задачата и от мен, направено с List. За да не променя оригиналните стойности на масива го копирам в втори масив от List<int>, превъртам масива с един цикъл for, сравнявам стойностите и ако първата стойност е по-голяма от втората е премахвам и нулирам цикъла. В примера даден в задачата най-малката стойност е 1, затова премахвам и всички елементи който са по-малки от 1.

Цък


от lyubo24 (249 точки)