CMP.2:5.1 - A join that initially loses the answer

For [-2,3,-1,4,-5], split into [-2,3,-1] and [4,-5]. Their best sums are 3 and 4. Keeping only those values would miss the crossing segment [3,-1,4], whose sum is 6.

The strengthened summaries are L=(0,1,2,3) and R=(-1,4,-1,4), ordered as (T,P,S,B). The join yields (-1,4,1,6). With attaining endpoints retained, it returns the segment from the second through fourth element. The user can now obtain the segment rather than merely knowing its value.

Changed condition: suppose the wanted segment may contain at most two elements. The former crossing winner has length three. The four maxima have discarded the sums of shorter candidate suffixes and prefixes. Add prefix and suffix results indexed by permitted length, combine only lengths whose sum is at most two, and keep the same restriction on internal best segments. In this case the answer becomes 4, attained by [4]. For a general limit k, a straightforward join over length pairs costs O(k²); the resource consequence can justify a different algorithm. Reusing the old four-value join would silently answer the earlier question.