Najdłuższy naprzemienny podciąg

Zadanie 9 z 10 · rozdział 24Trudność: 3 z 3dpsubsequencenaprzemienny

Treść zadania

Ciąg $x_1, x_2, \ldots, x_k$ jest naprzemienny (zygzakowaty), jeśli różnice między kolejnymi elementami są na przemian dodatnie i ujemne, czyli $x_1 < x_2 > x_3 < x_4 > \ldots$ albo $x_1 > x_2 < x_3 > x_4 < \ldots$

Ciąg jednoelementowy też jest naprzemienny. Dwa równe sąsiednie elementy psują naprzemienność (różnica 0 nie jest ani dodatnia, ani ujemna).

Otrzymujesz listę liczb całkowitych. Wyznacz długość najdłuższego naprzemiennego podciągu tej listy. Podciąg powstaje przez usunięcie z listy dowolnych elementów (być może żadnego) bez zmiany kolejności pozostałych — jego elementy nie muszą ze sobą sąsiadować na liście.

Dane wejściowe

  • 1. linia: n — długość listy
  • 2. linia: n liczb całkowitych oddzielonych spacjami

Dane wyjściowe

Jedna liczba całkowita — długość najdłuższego naprzemiennego podciągu.

Ograniczenia

  • 1 ≤ n ≤ 1000
  • elementy listy są z przedziału $[-10^6, 10^6]$

Uwagi

  • Podciągów jest $2^n$, więc sprawdzanie wszystkich jest wykluczone — w testach są listy z setkami elementów.
  • Programowanie dynamiczne: idąc po liście, pamiętaj długość najdłuższego naprzemiennego podciągu kończącego się wzrostem i kończącego się spadkiem. Gdy bieżący element jest większy od poprzedniego, podciąg „kończący się spadkiem” można przedłużyć wzrostem (i odwrotnie). Daje to czas $O(n)$; rozwiązanie $O(n^2)$ też zdąży.

Przykład

Wejście
8
1 -2 6 4 -3 2 -4 -3
Wyjście
7

Przykładowy najdłuższy podciąg naprzemienny (pominięto 4): $1 > -2 < 6 > -3 < 2 > -4 < -3$.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 24

Trudniejsze zadania na listach: przekształcenia w miejscu, sumy prefiksowe, kopiec i programowanie dynamiczne. Liczy się nie tylko poprawny wynik, ale też dobry algorytm — w testach są także długie listy, na których rozwiązanie „sprawdzające wszystkie możliwości” nie zdąży się wykonać.

Konwencje wspólne:

  • Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”. Tekst podany w input("…") jest ignorowany przez sprawdzarkę.
  • Lista liczb jest podawana w dwóch liniach: w pierwszej jest liczba elementów n, w drugiej n liczb całkowitych oddzielonych spacjami (o ile zadanie nie mówi inaczej).
  • Listę wynikową wypisuj w jednej linii, a jej elementy oddzielaj pojedynczą spacją (o ile zadanie nie mówi inaczej).
  • Indeksy liczymy od 0.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
1
42
Oczekiwane wyjście
1

Test 2

Nie uruchomiono
Wejście
4
5 5 5 5
Oczekiwane wyjście
1

Test 3

Nie uruchomiono
Wejście
5
1 2 3 4 5
Oczekiwane wyjście
2

Test 4

Nie uruchomiono
Wejście
5
1 3 2 4 3
Oczekiwane wyjście
5

Test 5

Nie uruchomiono
Wejście
7
1 1 2 2 1 1 3
Oczekiwane wyjście
4

Test 6

Nie uruchomiono
Wejście
10
1 17 5 10 13 15 10 5 16 8
Oczekiwane wyjście
7

Test 7

Nie uruchomiono
Wejście
2
-3 4
Oczekiwane wyjście
2

Test 8

Nie uruchomiono
Wejście
600
1 33 74 43 62 4 49 55 22 37 97 6 24 94 97 27 11 15 20 2 9 72 42 70 74 13 83 97 58 9 79 94 57 82 31 42 73 98 15 86 7 86 47 52 78 57 23 92 69 43 45 9 58 12 52 90 50 32 29 22 62 79 19 57 21 87 8 70 12 76 36 95 5 80 68 59 90 96 81 43 45 90 6 35 8 5 47 27 12 58 60 73 58 38 29 68 83 15 37 28 75 79 65 78 68 36 86 14 61 2 46 7 97 98 61 34 86 20 6 81 21 65 0 72 45 38 97 60 45 99 53 48 28 17 47 73 23 34 92 90 5 22 59 1 62 33 83 14 6 76 28 31 25 45 79 82 81 49 62 54 70 96 63 6 93 98 14 56 75 0 36 30 45 28 73 62 15 27 72 42 87 56 96 39 62 46 84 28 3 47 73 67 16 2 29 74 94 86 8 57 53 33 75 28 87 86 49 32 2 65 80 84 83 22 89 7 65 46 47 86 93 44 2 83 47 62 99 97 21 25 82 33 4 21 93 79 70 6 8 98 76 30 67 16 18 77 19 0 24 1 39 79 99 53 64 34 48 16 41 43 16 30 19 39 97 52 86 69 49 18 9 75 71 39 38 42 72 69 16 33 82 35 23 86 77 75 33 94 40 53 26 30 43 3 16 42 1 80 41 97 0 91 26 66 74 89 76 16 96 65 22 51 6 23 96 37 93 48 37 92 47 35 10 18 40 9 96 77 72 83 80 74 24 32 29 45 9 97 63 23 1 11 67 46 61 91 20 9 55 42 88 85 81 54 20 62 5 90 9 11 71 28 85 26 93 80 19 73 41 29 70 7 65 18 7 6 23 54 90 63 98 34 51 37 22 70 17 42 90 26 94 72 10 26 72 84 16 84 21 44 38 68 8 37 37 72 11 0 44 68 64 52 30 33 71 32 79 30 5 74 42 76 39 42 42 18 16 51 17 96 85 18 65 70 53 71 25 8 62 59 74 51 51 83 61 91 91 51 57 87 96 76 51 95 16 67 48 61 26 44 78 25 64 96 25 47 57 98 87 76 51 25 54 6 95 47 37 54 0 92 44 96 7 98 25 52 3 26 10 15 78 46 28 30 3 14 84 72 39 37 2 96 56 51 86 30 76 23 97 49 65 92 44 24 37 31 2 16 41 52 65 87 9 86 1 58 50 25 4 12 32 83 27 89 83 74 29 94 82 60 16 20 62 60 52 64 6 23 37 32 65 87 86 66 71 68 29 53 73 1 25 82 93 17 65 62 80 16 44 76 3 31 25 35 0 62 84 46 6 79 85 23 51 8 61 77 84 85 65 16 10 46 85 3 20 73 27 83 9 6
Oczekiwane wyjście
397
Uruchom z własnymi danymi