PARALLEL ALGORITHMS FOR MAXIMUM SUBSEQUENCE AND MAXIMUM SUBARRAY

Given a sequence Q of n numbers (positive and negative), the maximum subsequence of Q is the contiguous subsequence that has the maximum sum among all contiguous subsequences of Q. Given a two-dimensional array A of n n numbers (positive and negative), the maximum subarray of A is the contiguous subarray that has the maximum sum among all contiguous subarrays of A. We present two O(log n)-time parallel algorithms -- one for finding the maximum subsequence sum of a given sequence, and the other for finding the maximum subarray sum of a given array. The former is optimal on an EREW PRAM. The latter is optimal on a CREW PRAM, in the sense that the time-processor product matches the current sequential upperbound of O(n³)