他的证明应该是有问题的.所以我特意写下这篇讨论避免后续的读者被其误导.

他证明了不能走回头路,但是按照它这种证明方式实际上就是可以走回头路的.考虑1 5 4 6 3 2 7这样的序列,假设我们的$i$在5这个位置,$k$1的位置,$j$在7的位置,显然要回到1最后到7更优.所以根本就不能这么证明,正确的证明方式应该得出如果$i$想要往回跳到$k$,再从$k$跳到$j$这样是最优的,那么我们在$pos$位置($pos$能跳到$i$和$k$的时候)就可以直接跳到$k$而不是跳到$i$这个点.假设$pos$不能直接跳到$k$,也就是说$pos$跳到$i$的花费小于$pos$跳到$k$的花费,此时假设$a[pos]>a[k]>a[i]$,那么对于$i$的下一个目标来说,如果它作为区间最大值,那么$i$更为优秀(因为$i$比$k$值小,$k$想跳到下一个目标必须经过$i$);如果它作为区间最小值,那么$pos$显然更为优秀,因为它是全局最大值.所以此时无论如何都不会轮到$k$(都与最初的走回头路矛盾).(注意上述的证明也不是非常严谨,我偷懒了,只是举了其中的一个例子,但是事实上如果想要完整证明只要照着上述例子的证明方式进行分类讨论即可)