白駿11054号最長のVitonic部分数列

白駿11054号
最長の2進数列

この問題は有名なLongest Increating Subsequenceを利用して解決できる.
まず、入力と出力の例を見てみましょう.

1 5 2 1 4 3 4 5 2 1 이 주어졌다.
이 때, 두 번째 원소에서의 바이토닉 부분 수열의 길이를 살펴보면

1 5
5 4 3 2 1 의 두 부분으로 나누어서 볼 수 있다.

15はインデックス内のLISです.
5 4 3 2 1はこのインデックスで逆思考が可能なLISである.
つまり.
最長のバイナリ部分数列は,インデックス中のLISと逆LISをそれぞれ求めて加算した数列である.
ソースコードで確認しましょう.

s f配列の既存リストから求めた各インデックス上のLIS長.
s b配列はドメインリストから求めた各インデックスのLIS長である.
その後,最後の複文では,各長さを増やしてニック数列の長さを求める.
1を減算するのは、インデックスの要素が2回加算されるためです.