Zadanie 1. Najdłuższy niemalejący podciąg

Problem najdłuższego niemalejącego podciągu jest klasycznym problemem optymalizacyjnym. Oznacza to, że posiada on własność optymalnej podstrukturywłasność optymalnej podstrukturywłasność optymalnej podstruktury. Problem ten jest następujący: mamy ciąg n liczb całkowitych aIndeks dolny 1 Indeks dolny koniec1,aIndeks dolny 2 Indeks dolny koniec2,...,aIndeks dolny n Indeks dolny koniec_n , należy znaleźć najdłuższy podciąg bIndeks dolny 1 Indeks dolny koniec1,bIndeks dolny 2 Indeks dolny koniec2,...,bIndeks dolny k Indeks dolny koniec_k ciągu aIndeks dolny i Indeks dolny koniec_i, że dla każdego i>0 prawdą jest bIndeks dolny i Indeks dolny konieci≤ bIndeks dolny i+1 Indeks dolny koniec_i+1.

Przykładowo: dla ciągu [4, 6, 3, 9, 1, 0, 1, 4, 7, 2, 5, 8, 9, 3, 5] maksymalny niemalejący podciąg to [1, 1, 4, 7, 8, 9].

W pliku liczby.txt znajduje się 1000 liczb całkowitych dodatnich, zapisanych dziesiętnie, maksymalnie sześciocyfrowych. Każda liczba umieszczona jest w osobnym wierszu.

Napisz program(-y), za pomocą którego(-ych) rozwiążesz poniższe zadanie. Do oceny oddaj dokument wyniki.txt z rozwiązaniami  oraz pliki źródłowe programów wykorzystanych do uzyskania rozwiązania.

Znajdź najdłuższy niemalejący ciąg liczb występujących w kolejnych wierszach pliku liczby.txt. Podaj pierwszy element tego ciągu oraz liczbę jego elementów. Możesz założyć, że jest jeden taki ciąg.

Dla przykładowych danych:

 23156 

 1231 

 1345 

 1456 

 1456 

 897 

najdłuższy niemalejący ciąg liczb rozpoczyna się liczbą 1231 i składa się z 4 elementów.

Zadanie pochodzi ze zbioru zadań  maturalnych CKE (zadanie nr 62.2).

Przykładowe rozwiązanie:

plik=open("liczby.txt")
liczby=[]
for i in plik:
    liczby.append(int(i))
    
   
poprzednia = -1
pierwszy = -1
dlugosc_ciagu = 0
naj_dlugosc_ciagu = 0
naj_pierwszy = -1

for liczba in liczby:
    if liczba>=poprzednia:
        dlugosc_ciagu += 1
    else:
        pierwszy = liczba
        dlugosc_ciagu = 1;
    if dlugosc_ciagu > naj_dlugosc_ciagu:
        naj_dlugosc_ciagu = dlugosc_ciagu
        naj_pierwszy = pierwszy
    poprzednia = liczba
    
plik.close()

print(f"najdluzszy ciag zaczyna sie od elementu  {naj_pierwszy} i ma {naj_dlugosc_ciagu} elementów") 
   

Odpowiedź do zadania:

Najdłuższy ciąg zaczyna się od elementu 639 i ma 6 elementów