A divide-and-conquer maximum-subarray solution lets every range report a summary of four numbers: total (the sum of the whole range), prefix (the best sum of a non-empty prefix), suffix (the best sum of a non-empty suffix) and best (the best sum of any non-empty subarray inside the range).
Write mergeSummaries(left, right) that takes the summaries of two adjacent ranges, left first, and returns the summary of the two ranges joined.
- A one-element range with value
v has the summary { total: v, prefix: v, suffix: v, best: v } - Return a new object with exactly those four keys, and do not change the arguments
- It must take O(1) time: no loops
- Values may be negative, and every prefix, suffix and subarray must contain at least one element