Annettuna on lista, josta tulee poimia mahdollisimman monta lukua. Ensimmäinen luku saa olla mikä tahansa listan luku ja tämän jälkeen seuraavan poimitun luvun tulee olla tasan yhden suurempi kuin edellinen. Kuinka monta lukua voidaan näin korkeintaan poimia?
Voit olettaa, että listalla on enintään 10^5 lukua ja että jokainen luku on väliltä 1 \dots 10^9. Tavoitteena on, että algoritmin aikavaativuus on O(n) tai O(n \log n).
Toteuta tiedostoon interval.py funktio count, joka ilmoittaa, montako lukua listalta voidaan enintään poimia halutulla tavalla.
def count(t):
# TODO
if __name__ == "__main__":
print(count([1, 1, 1, 1])) # 1
print(count([10, 4, 8])) # 1
print(count([7, 6, 1, 8])) # 3
print(count([1, 2, 1, 2, 1, 2])) # 2
print(count([987654, 12345678, 987653, 999999, 987655])) # 3
Selitys: Listalta [10, 4, 8] voidaan poimia vain yksi luku, sillä minkään kahden luvun erotus ei ole tasan 1. Listalta [7, 6, 1, 8] on mahdollista poimia 3 lukua järjestyksessä 6, 7 ja 8.