Podciągi


Podciąg to wybrane element ciągu wyjściowego np.: liczby 3, 2, 5, 7 tworzą podciąg ciągu 3, 1, 2, 5, 7, 4. Jeśli elementy podciągu wystepują w ciągu wyjściowym obok siebie to taki podciąg nazywamy podciągiem spójnym. Na przykład ciąg 1,2,5 jest podciągiem spójnym ciągu 3,1,2,5,7,4

Najdłuższy spójny podciąg niemajejący

W podciągu niemalejącym każdy kolejny element jest wiekszy lub równy poprzedniemu. Na przykąłd w ciągu: 3,1,2,5,7,4 możem wyróżnić następujace spójne podciągi niemalejące:

  • 1,2
  • 1,2,5
  • 1,2,5,7
  • 2,5
  • 2,5,7
  • 5,7

    Specyfikacja

    Dane:
    A[0..n-1] - tablica n liczb całkowitych
     
    Wynik
    maks_dl - długość najdłuższego spójnego podciągu niemalejacego w tablicy A.
     
    Lista kroków algorytmu:
     
    Krok 0. Wczytaj wyrazy ciągu do tablicy A[]
    Krok 1. Przypisz maks_dl = 1
    Krok 2. Przypisz akt_dl=1
    Krok 3. Dla i=1,2,..., n-1 wykonuj krok 4
    Krok 4. Jeśli A[i] >= A[i-1] to akt_dl=akt_dl+1, jeśli akt_dl > maks_dl to maks_dl = akt_dl i przejdź do kroku 3, w przeciwnym przypadku akt_dl = 1 przejdź do kroku 3
    Krok 5. Wypisz maks_dl i zakończ algorytm




    Ćwiczenia

    1. Napisz program wypisujący długość najdłuższego spójnego podciągu niemalejacego
    2. Napisz program wypisujacy najdłuższy spójny podciąg niemalejący.
    3. Napisz program znajdujący najwiekszą sume podciągu spójnego. wypisz ten podciąg.
    4. Napisz program wypisujacy z ciągu n-licz całkowu=itych wszystkie podciągi spójne o podanej (wczytanej) sumie.

    Zadanie

    Napisz program, który wypisze najdłuższy spójny rosnący ciąg liczb całkowitych. Jeśli takich ciągów jest kilka, program powinien wypisać pierwszy.
    Dane wejściowe
    W pierwszym wierszu jedna liczba n określająca ilość liczb w ciągu (n mniejsze od 1000000) .
    W drugim wierszu n liczb całkowitych z przedziału [0..1000].
    Dane wyjściowe
    Szukany ciąg liczb.
    Przykład
    Wejście
    10
    1 2 3 3 2 4 5 7 0 9

    Wyjście
    2 4 5 7


    Wróć do spisu tematów