Let (S n ) n≥0 be a correlated random walk on the integers, let M 0 ≥ S 0 be an arbitrary integer, and let M n = max{M 0, S 1,…, S n }. An optimal stopping rule is derived for the sequence M n - nc, where c > 0 is a fixed cost. The optimal rule is shown to be of threshold type: stop at the first time that M n - S n ≥ Δ, where Δ is a certain nonnegative integer. An explicit expression for this optimal threshold is given.