We address a generalization of change point detectionwith the purpose of detecting the changelocations and the levels of clusters of a piecewiseconstant signal. Our approach is to model itas a nonparametric penalized least square modelselection on a family of models indexed over thecollection of partitions of the design points andpropose a computationally efficient algorithm toapproximately solve it. Statistically, minimizingsuch a penalized criterion yields an approximationto the maximum a-posteriori probability(MAP) estimator. The criterion is then analyzedand an oracle inequality is derived usinga Gaussian concentration inequality. The oracleinequality is used to derive on one hand conditionsfor consistency and on the other hand anadaptive upper bound on the expected square riskof the estimator, which statistically motivates ourapproximation. Finally, we apply our algorithmto simulated data to experimentally validate thestatistical guarantees and illustrate its behavior.