算法的正确性以在数组中找到最大值

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]，因为仅处理一个元素，它是最大的。

诱导假设：i=k<n-1,假定算法正确找到最大的算法。

归纳步骤：i=k+1，令ans_{i}表示由算法获得的最大元素到i步骤，然后ans'_{i}表示Array A[0:i-1]的另一个最大元素。

然后来自诱导假设， ans_{k} = ans'_{k}

现在，为了矛盾，假设ans_{k+1} < ans'_{k+1}

现在，我应该如何继续显示这种矛盾？

有什么建议吗？我应该改变这种方法吗？

Answer 1

其中n为零，我们获得 - infinity。其中n是一个或更高的，我们获得max2（ans_（n-1），a [n-1]）。因此，诱导有效，除非max2（-infinity，x）返回-Infinity，如果[n-1] = nan，它可能会这样。矛盾步骤实际上表明该功能可能并不像应有的那样严格。