A Parallel Array Scanning Algorithm

Suppose we are given a vector X of n real numbers and we want to find the maximum sum found in any contiguous subvector of X. In Jon Bentley's article [l] on algorithm design and technique, a simple vector scanning problem and a series of progressively more efficient algorithms to solve this problem were discussed in some detail. Clearly, any algorithm must visit each location of X at least once and consequently a lower bound on the running time for problem is 0(n), which is in fact attainable as Bentley’s paper illustrates. However, the original motivation for this problem was the analagous two dimensional problem for an n x n array. That is, find the maximum sum contained in any contiguous rectangular subarray. Currently, the fastest algorithm obtained for this problem is O(n ³ )[2] ; the theoretical lower bound would be at least 0(n ² ). In this note, we will present a parallel processing approach to this problem which results in excess of one order of magnitude speed up for large problems in the 0(n ³ ) algorithm.