Both the cost function of Section 2.2 and the feature representation of Section 2.3 are defined over a short sequence of segment boundaries.
using the Markovian property, one can perform the above maximization step efficiently via a dynamic programming algorithm.