= Longest bitonic contiguous segment
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.
Back to article page
