In this paper, we present a parallel algorithm for the maximum convex sum (MCS) problem, which is a generalization of the maximum subarray (MSA) problem. In the MSA problem, we find a rectangular portion within the given data array that maximizes the sum in it. The MCS problem is to find a convex shape instead of a rectangular shape that maximizes the sum. For the MSA problem,  O ( n ) time parallel algorithms are already known on an ( n, n ) 2D array of processors. For the MCS problem, we achieve the same time bound of  O ( n ) on an ( n, n ) 2D array of processors. We provide rigorous proofs for the correctness of our parallel algorithm based on Hoare logic and also provide some experimental results of our algorithm that are gathered from the Blue Gene/P super computer.
['Sung Eun Bae', 'Tong-Wook Shinn', 'Tadao Takaoka']
An efficient parallel algorithm for the maximum convex sum problem