単調増加部分列の長さ
基本は、与えられた数列を順番にスキャンしながら、
・dp[k] = v # 長さ k の部分列を取り出した際の最後の値（の最小値）が v
を更新していくという方法です。dp は、
・dp = [-Inf, Inf, Inf,..., Inf]
で初期化しておきます。
dp は単調増加になるので、n 番目の要素 A[n] を考えた際に、A[n] よりギリギリ小さい v の位置は、二分探索で高速に検索できます。
・index = (A[n] よりギリギリ小さい v の位置) + 1
として、
・dp[index] = min(dp[index], A[n])
で、dp が更新できます。次のように、非常にシンプルに実装が可能です。
dp = [10**30] * (N+1) # dp[長さ] = 最後の値（の最小値） dp[0] = -10**30 for i in range(N): index = bisect.bisect_left(dp, A[i]) dp[index] = min(dp[index], A[i])
最後に dp[k] < Inf である最大の k が単調増加部分列の最大の長さを与えます。
A[n] を採用した場合の部分列の長さ
冒頭の問題は、前半が単調増加、後半が単調減少という組み合わせになっているので、
・単調増加列の末尾が A[n] だった場合の単調増加列の長さ ---- (1)
・単調減少列の頭が A[n] だった場合の単調減少列の長さ ---- (2)
という情報が必要になります。
(1) については、上記の dp とは別に、
・dp2[i] = k # A[i] を末尾とした場合の単調増加列の長さは k
という情報を記録していきます。さきほどの実装を次のように修正すればOKです。
dp1 = [10**30] * (N+1) # dp1[長さ] = 最後の値（の最小値） dp1[0] = -10**30 dp2 = [-1] * N # dp2[i] = A[i] を末尾とした場合の長さ for i in range(N): index = bisect.bisect_left(dp1, A[i]) dp1[index] = min(dp1[index], A[i]) dp2[i] = index
(2) については、A を反転させて (1) を求めて得られたものをもう一回反転すればOKですね。
A.reverse() dp3 = [10**30] * (N+1) dp3[0] = -10**30 dp4 = [-1] * N for i in range(N): index = bisect.bisect_left(dp3, A[i]) dp3[index] = min(dp3[index], A[i]) dp4[i] = index dp4.reverse()
(1)(2) の情報があれば、折り返し点を A[0], A[1], ... とした場合、それぞれでの最長部分列（の合計）を個別に計算することができます。
