最長増加部分列がイマイチ分からない

蟻本を少しずつ進めています。p.63～p.65の最長増加部分列の説明なのですが、自分にはどうも自明には思えなくて、そこで少し停止しています。dpは単調増加であるとか、更新できる要素は高々1個しかないとか、そこらへんが解説なしに進んでいってしまうので、ハテ？という状態。かといって証明しようにもどうしたらよいか分からんので困った感じです。それは正しいものと受け入れて次に進んでしまえば速いのですが、なんかスッキリしない感じ。うーんどうしたものか。