Vind het maximum — het idee

Leerdoel: je begrijpt hoe je de grootste waarde uit een lijst haalt door er één keer doorheen te lopen. Nog geen Python — eerst snappen.

Het verhaal

Je staat met je klas op het schoolplein. De leraar vraagt: "wie is de langste?" Niemand heeft een meetlat. Wat doe je?

Een logische aanpak:

1. Loop naar de eerste persoon en onthoud die lengte als "langste tot nu toe".
2. Loop naar de tweede. Is die langer, onthoud dan die lengte; zo niet, dan verandert er niets.
3. Herhaal voor de derde, vierde, vijfde, …
4. Aan het eind ben je langs iedereen geweest en weet je wie de langste is.

Dit is vind het maximum in één zin: onthoud de grootste tot nu toe en update onderweg.

Visualisatie

We zoeken het maximum in deze lijst:

lijst:  [ 3 , 7 , 2 , 9 , 4 ]
index:    0   1   2   3   4

start:  max = 3    we beginnen met het eerste element

vergelijk 3 met max=3:  niet groter  ->  max blijft 3
vergelijk 7 met max=3:  groter       ->  max = 7
vergelijk 2 met max=7:  niet groter  ->  max blijft 7
vergelijk 9 met max=7:  groter       ->  max = 9
vergelijk 4 met max=9:  niet groter  ->  max blijft 9

eind:   maximum = 9    in 5 vergelijkingen

Je bekijkt elk element precies één keer. De eerste vergelijking is er een die een mens niet zou maken: het eerste element wordt met zichzelf vergeleken. Dat komt doordat de lus straks gewoon bij het begin van de lijst start, en het kost niets.

Het accumulator-patroon

Dit is een patroon dat je in heel veel algoritmes terugziet:

1. Begin met een startwaarde; hier is dat het eerste element.
2. Loop door de rest van de lijst.
3. Werk je waarde bij zodra de nieuwe iets bijzonders is, hier: groter.
4. Aan het eind heb je het antwoord.

Je accumuleert (verzamelt) informatie tijdens de doorloop. Vandaar de naam.

Wat als de lijst leeg is?

Dan is er geen maximum, want er is niets om te vergelijken. Veel algoritmes geven dan een speciale waarde terug (None), of crashen met een foutmelding. We bespreken dit later expliciet.

Hoe snel is dit?

Voor n elementen doet dit algoritme n vergelijkingen, één per element. Dat heet O(n): lineair in de lengte. Minder dan n − 1 kan sowieso niet, want je moet elk element minstens één keer hebben gezien om zeker te weten dat het niet het maximum is.

Zo bouw je het op

De code bouw je in kleine stappen, elk op een eigen pagina in de map "Bouwen, stap voor stap":

1. Bouwsteen 1 — vergelijken en bijhouden
2. Bouwsteen 2 — door de lijst lopen en updaten
3. Bouwsteen 3 — een veilige startwaarde

Daarna zet je alles samen in Het complete algoritme, en ga je het aanpassen en zelf bouwen.

Door naar bekijk het algoritme.