Maksimilista

Tehtäväsi on toteuttaa luokka, joka pitää yllä listaa luvuista sekä tarjoaa metodin, jonka avulla voidaan hakea tehokkaasti listan suurin luku.

Toteuta tiedostoon maxlist.py luokka MaxList, jossa on seuraavat metodit:

• append(number): lisää luku listan loppuun
• max(): ilmoita listan suurin luku

Voit olettaa, että listalla on vähintään yksi luku, kun metodia max kutsutaan. Kummankin metodin tulee toimia tehokkaasti ajassa $O(1)$.

class MaxList:
    def __init__(self):
        # TODO

    def append(self, number):
        # TODO

    def max(self):
        # TODO

if __name__ == "__main__":
    numbers = MaxList()

    numbers.append(1)
    numbers.append(2)
    numbers.append(3)
    print(numbers.max()) # 3

    numbers.append(8)
    numbers.append(5)
    print(numbers.max()) # 8

Tässä listalle lisätään ensin luvut $1$, $2$ ja $3$, minkä jälkeen listan sisältö on $[1,2,3]$ ja suurin luku on $3$. Tämän jälkeen lisätään vielä luvut $8$ ja $5$, minkä jälkeen listan sisältö on $[1,2,3,8,5]$ ja suurin luku on $8$.

Voit tutkia ratkaisusi tehokkuutta seuraavan testin avulla. Tässäkin tapauksessa koodin tulisi antaa vastaus välittömästi.

    numbers = MaxList()
    total = 0
    for i in range(10**5):
        numbers.append(i * 999983 % 10**9)
        total += numbers.max()
    print(total) # 99498381797517