Saat syötteenä listan, jossa on jokin lukujen 1 \dots n permutaatio. Tehtäväsi on laskea listan vuorottelevien osajonojen lukumäärä.
Tässä vuorotteleva tarkoittaa sitä, että osajonossa seuraava luku on aina vuorotellen pienempi tai suurempi kuin edellinen. Toisin ilmaistuna vuorotteleva osajono on sellainen, joka ei sisällä ainuttakaan vähintään kolmen pituista kasvavaa eikä vähenevää osajonoa.
Tavoitteena on, että algoritmin aikavaativuus on O(n).
Toteuta tiedostoon alternation.py funktio count, joka palauttaa vuorottelevien osajonojen lukumäärän.
def count(t):
# TODO
if __name__ == "__main__":
print(count([1,2,3,4])) # 7
print(count([1,4,2,5,3])) # 15
print(count([7,2,1,3,5,4,6])) # 17
Selitys: Listalla [1,2,3,4] vain yhden (4 kpl) ja kahden (3 kpl) pituiset osajonot kelpaavat, sillä pidemmissä osajonoissa on aina kaksi kertaa peräkkäin oikeammanpuoleinen luku suurempi kuin edellinen. Listalla [1,4,2,5,3] jokainen osajono on kelvollinen, sillä jokainen luku listalla on aina vuorotellen suurempi tai pienempi kuin edellinen.