  Given an array A of n real numbers, the maximum subarray problem is to find a
contiguous subarray which has the largest sum. The k-maximum subarrays problem
is to find k such subarrays with the largest sums. For the 1-maximum subarray
the well known divide-and-conquer algorithm, presented in most textbooks,
although suboptimal, is easy to implement and can be made optimal with a simple
change that speeds up the combine phase. On the other hand, the only known
divide-and-conquer algorithm for k > 1, that is efficient for small values of
k, is difficult to implement, due to the intricacies of the combine phase. In
this paper we give a divide- and-conquer solution for the k-maximum subarray
problem that simplifies the combine phase considerably while preserving the
overall running time.
  In the process of designing the combine phase of the algorithm we provide a
simple, sublinear, O($k^{1/2} log^3 k$) time algorithm, for finding the k
largest sums of X + Y, where X and Y are sorted arrays of size n and $k <=
n^2$. The k largest sums are implicitly represented, and can be enumerated with
an additional O(k) time. To our knowledge, this is the first sublinear time
algorithm for this well studied problem.
  Unlike previous solutions, that are fairly complicated and sometimes
difficult to implement, ours rely on simple operations such as merging sorted
arrays, binary search, and selecting the $k^{th}$ smallest number in an array.
We have implemented our algorithms and report excellent performance on test
data.
