  Given a time series in $R^n$ with a piecewise constant mean and independent
noises, we propose an exact dynamic programming algorithm to minimize a least
square criterion with a multiscale penalty promoting well-spread changepoints.
Such a penalty has been proposed in Verzelen et al. (2020), and it achieves
optimal rates for changepoint detection and changepoint localization. Our
proposed algorithm, named Ms.FPOP, extends functional pruning ideas of Rigaill
(2015) and Maidstone et al. (2017) to multiscale penalties. For large signals,
$n \geq 10^5$, with relatively few real changepoints, Ms.FPOP is typically
quasi-linear and an order of magnitude faster than PELT. We propose an
efficient C++ implementation interfaced with R of Ms.FPOP allowing to segment a
profile of up to $n = 10^6$ in a matter of seconds. Finally, we illustrate on
simple simulations that for large enough profiles ($n \geq 10^4$) Ms.FPOP using
the multiscale penalty of Verzelen et al. (2020) is typically more powerfull
than FPOP using the classical BIC penalty of Yao (1989).
