= Solution
For each $m$, the displayed objective is the sum of the minimized linear-regression residual sums of squares on the prefix $1{:}m$ and suffix $(m+1){:}n$. Precompute prefix sums of
$$
X_i,quad Y_i,quad X_i^2,quad X_iY_i,quad Y_i^2.
$$
This requires $O(n)$ operations. The corresponding five sums over a suffix are obtained by subtracting a prefix sum from the total.
For any block of $k$ observations, these raw sums give in constant time
$$
S_{xx}=\sum x_i^2-\frac{(\sum x_i)^2}{k},
\quad
S_{xy}=\sum x_iy_i-\frac{(\sum x_i)(\sum y_i)}{k},
\quad
S_{yy}=\sum y_i^2-\frac{(\sum y_i)^2}{k}.
$$
By the formula for the <residual sum of squares in simple linear regression>, its minimized loss is
$$
S_{yy}-\frac{S_{xy}^2}{S_{xx}}.
$$
\b[Hence both losses for a proposed $m$ take constant time. Evaluating their sum for $m=2,\ldots,n-2$ and keeping the minimum is another $O(n)$ scan, so the complete minimization uses $O(n)$ computations.]
Back to article page
