シーケンスの最大値探索

しかし、なんやかんやでいろんなところで役に立つ

A: 長さnのT型のシーケンス

n > 0

各要素に二項関係<が定義できる。

code:cpp

int32_t M = A0;

for (const T a:A) { M = std::max(M, a); }

$ i番目までの要素を含む集合を$ A_iとする。

$ i番目の要素を$ a_iとする。

$ \max A_{i+1} = \max \{ \max A_i, a_{i+1} \}が成立するため成立する。

数学的帰納法によって証明可能

加えて、$ A = A_nであることも重要

$ i回目(1-origin)のループでは$ \max A_iが求められている状態と言える。