\(dp_{i,j}\)を\(A_1,A_2,…,A_j\)を\(i\)個に分けた時の種類数の和の最大値とします。
\(dp_{i,j}=max_{0 \leq k < j} dp_{i-1,k}+(A_{k+1},…,A_jの種類数)\) と更新できます。
ここで、区間種類数はそれぞれの値が含まれるかどうかの01列の区間maxの和で表せます。区間maxはmongeでmongeの和もmongeであることから区間種類数もmongeです。したがって(スライドアクセスの)monotone minimaで\(dp_i\)から\(dp_{i+1}\)への更新を\(O(NlogN)\)で行えます。答えは\(dp_{3,N}\)です。
実装例