Правильность алгоритма для нахождения максимума в массиве

Question

Я хочу показать правильность «Алгоритм для нахождения максимального элемента в массиве» с использованием индукции и противоречия.

ans=-infinity 
for (i=0; i<n; i++) 
    ans= max(ans, A[i]) 

где A[0:n-1] является массивом и max функция возвращать максимум двух аргументов.

Что я делаю:

Базовый случай: i=0, ans= max(-infinity,A[0])=A[0], так как только один элемент был processsed, это максимум.

Индукционная гипотеза: i=k<n-1, Предположим, что алгоритм правильно находит максимум до k итераций.

Индуктивный шаг: i=k+1, пусть ans_{i} обозначают максимальный элемент, полученный с помощью алгоритма Шифрование до i шагов, и пусть ans'_{i} обозначают еще один максимальный элемент из массива A[0:i-1].

Тогда из индукционной hypothsis, ans_{k} = ans'_{k}

Теперь, ради противного, предположим ans_{k+1} < ans'_{k+1}

Теперь, как я должен продолжить, чтобы показать это противоречие?

Любое предложение? Должен ли я изменить этот подход?

Answer 1

Где n равно нулю, мы получаем -инфекцию. Где n одно или выше, мы получаем max2 (ans_ (n-1), A [n-1]). Итак, индукционные работы, если max2 (-infinity, x) не возвращает -infinity, что может быть, если A [n-1] = NaN. Шаг противоречия на самом деле показывает, что функция, возможно, не является строгой, как должно быть.