Perché questa è una prova per contraddizione per questo algoritmo? Non è invece una prova diretta?

Question

Prima diapositiva: trova max (a)

1. // Input: A [1..N] - Un array di numeri interi
2. // output: un elemento m di a tale che m> = a [j], per tutti 1 <= j <= A.Length
3. max = a [j == 1
4. per J = 2 a A.Length
5. Se max <a [j
6. max = a [j
7. Restituisce Max

Seconda diapositiva: prova per contraddizione

Prova: supponiamo che l'algoritmo non sia corretto. Quindi per qualche input A, entrambi:

1. max non è un elemento di a o
2. A ha un elemento a [j] tale che max <a [j

Max viene inizializzato e assegnato agli elementi di A - Quindi (1) è impossibile.

Dopo l'iterazione J -Th del Loop For (righe 4 - 6), max> = a [j]. Dalle righe 5,6 Max aumenta solo. Pertanto, dopo la risoluzione, max> = a [j] che contraddice (2).

Fine delle diapositive

Questo algoritmo (prima diapositiva) trova l'elemento massimo nell'array. Questa è una prova per contraddizione. Questo algoritmo non è già dimostrato quando arriva max> = a [j] nell'ultima riga della seconda diapositiva. È che contraddice (2) anche necessario? Perché nella seconda diapositiva hai mostrato che Max è nell'array e poi hai incontrato la condizione di un maxium m: un elemento m di a tale che m> = a [j] per tutti 1 <= j <= a.length.

Questa sembra essere due prove in una. E dal momento che mi sembra che la prova diretta si verifichi prima, quindi la prova per contraddizione è ridondante e quindi non necessaria. Mi manca qualcosa qui? È solo una prova per contraddizione? O è invece una prova diretta?

L'immagine sotto è solo le diapositive 1 e 2 che ho trascritto sopra. Dalla York University.