\(\{ Y_i \}\) は昇順にソートする.

\(\{ Y_i \}\) をある数値を境に 2 つのグループに分け, それぞれのグループの距離の総和が最小になるような値を選ぶ. \(N-1\) 個グループ分けの種類ごとにこれを計算して距離の総和が最も小さい分け方を採用する.

距離の総和を最小にするためには中央値を選べばいい. 総和の計算は累積和をあらかじめ計算しておく.