Track the length of the constant suffix of the scanned prefix:
best = 0; run = 0
for i = 0,...,n-1:
if i == 0 or a[i] != a[i-1]: run = 1
else: run = run+1
if run > best: best = run
return bestThe condition is evaluated with short-circuit logic, so
a[-1] is never accessed. After processing index , run is the longest constant segment of an array ending there and best is the longest anywhere in . A maximal constant segment either extends the preceding suffix or starts at a changed value, proving the update. Empty input returns zero. Time is , with constant auxiliary storage.Add
bestStart = 0 initially and, whenever a strictly longer run is found, recordbest = run
bestStart = i-run+1Then is a plateau of the returned maximum length. Keeping the old answer on equal lengths selects the earliest maximum. The loop invariant from part (a) gains the assertion that the recorded interval realizes
best; time and auxiliary-space bounds are unchanged. For empty input use the empty interval at zero.Increasing here means nondecreasing, so equal neighbors remain in the same run. Change only the suffix-reset test:
best = 0; run = 0; bestStart = 0
for i = 0,...,n-1:
if i == 0 or a[i] < a[i-1]: run = 1
else: run = run+1
if run > best:
best = run; bestStart = i-run+1
return (bestStart,best)After index ,
run is the longest nondecreasing suffix of the prefix and the recorded interval is a longest nondecreasing segment seen so far. The adjacent-comparison condition implies the all-pairs condition by transitivity. The scan uses time and auxiliary space. Empty input yields length zero because no nonempty increasing segment exists.Ignore zero adjacent differences. A segment is bitonic in the question's peak-or-valley sense precisely when its remaining difference signs change at most once. Keep the earliest starts of the current monotone suffix and current bitonic suffix:
if n == 0: return (0,0)
monoStart = 0; bitStart = 0
lastDir = 0; lastStrictEnd = 0
best = 1; bestStart = 0
for i = 1,...,n-1:
dir = compare(a[i],a[i-1]) // -1, 0, or +1
if dir != 0:
if lastDir != 0 and dir != lastDir:
bitStart = monoStart
monoStart = lastStrictEnd
lastDir = dir
lastStrictEnd = i
length = i-bitStart+1
if length > best:
best = length; bestStart = bitStart
return (bestStart,best)After processing ,
lastDir is the most recent nonzero difference sign; lastStrictEnd is its endpoint. monoStart is the earliest start of a suffix with only that nonzero direction, and bitStart is the earliest start of a suffix with at most one sign change. The best recorded interval realizes the largest such length over the whole scanned prefix.A zero difference changes neither direction. On reversal, a valid new bitonic suffix may retain the entire old monotone suffix, but cannot retain a preceding opposite-direction run as well, which would create two changes. Hence its earliest start is the old
monoStart. The new monotone suffix starts at lastStrictEnd, retaining the intervening plateau. This proves the update and explains why merely starting at loses valid overlapping segments. The longest bitonic contiguous segment algorithm uses time and auxiliary space; the sample's maximum length is 5. Articles by others on the same topic
There are currently no matching articles.