Creasta unui tablou bidimensional

Ce înseamnă că un șir este munte

Definiția cere trei lucruri deodată: vârful să fie strict mai mare decât toți ceilalți termeni, partea dinaintea lui să crească strict, iar partea de după el să scadă strict.

Prima condiție are o consecință care simplifică rezolvarea: vârful este maximul șirului, iar acest maxim este unic. Dacă valoarea maximă ar apărea de două ori, niciuna dintre apariții nu ar fi strict mai mare decât cealaltă, deci șirul nu ar fi munte.

Șirul poate începe chiar cu vârful sau se poate încheia cu el — enunțul spune „dacă există” tocmai pentru aceste cazuri. Un șir strict crescător este munte, cu vârful pe ultima poziție; unul strict descrescător este munte, cu vârful pe prima.

Verificarea se face deci în trei pași: se determină poziția maximului, se verifică creșterea strictă până la ea și se verifică descreșterea strictă după ea. Nu mai este nevoie de o verificare separată a unicității maximului: dacă maximul apare de mai multe ori, una dintre cele două parcurgeri întâlnește două valori egale alăturate și se oprește.

Descrierea algoritmului în limbaj natural

Se citesc dimensiunea n și cele n·n elemente ale tabloului.

Pentru fiecare linie k se apelează subprogramul varf. În interiorul lui se determină mai întâi poziția celui mai mare element de pe linie, parcurgând linia de la stânga la dreapta și reținând poziția primei apariții a maximului. Se parcurge apoi partea dinaintea acestei poziții și se verifică dacă fiecare element este strict mai mare decât cel dinaintea lui; dacă nu, subprogramul returnează 0. Se parcurge partea de după poziția maximului și se verifică dacă fiecare element este strict mai mic decât cel dinaintea lui; dacă nu, se returnează tot 0. Dacă amândouă verificările trec, se returnează poziția maximului.

În programul principal se rețin valorile întoarse pentru cele n linii. Dacă vreuna dintre ele este 0, o linie nu este munte, deci tabloul nu formează creastă și se afișează NU.

Dacă toate liniile sunt munți, se verifică a doua condiție: pentru fiecare pereche de linii consecutive, diferența dintre coloanele vârfurilor trebuie să fie, în valoare absolută, cel mult 1 — aceasta este scrierea condiției „pe aceeași coloană sau pe coloane consecutive”. Dacă o pereche nu o îndeplinește, se afișează NU.

Dacă amândouă condițiile sunt îndeplinite pentru tot tabloul, se afișează DA.