Bitonic segment

Here a bitonic contiguous segment may be weakly increasing then weakly decreasing, or the reverse. Equivalently, remove zero signs from its adjacent differences: the remaining signs change at most once. This convention includes monotone and constant segments. A plateau can lie at the shared boundary between two directions, so maximal bitonic segments can overlap across that entire plateau.

A linear time scan can retain the earliest start of the current monotone suffix, the earliest start of the current bitonic suffix, the most recent nonzero direction and the endpoint of its most recent strict step. At a strict direction reversal, the new bitonic suffix begins at the old monotone start; the new monotone suffix begins at the old strict-step endpoint. Zero differences leave these boundaries unchanged. The suffix invariants show that no longer valid suffix is discarded, and recording the largest length gives a global optimum using constant auxiliary storage.