APPLICATION OF BROADCASTING WITH SELECTIVE REDUCTION TO THE MAXIMAL SUM SUBSEGMENT PROBLEM

作     者：S. G. AKL G. R. GUENTHER 

作者机构：Department of Computing and Information Science Queen's University Kingston Ontario Canada Department of Mathematics and Computer Science Laurentian University Sudbury Ontario Canada 

出 版 物：《International Journal of High Speed Computing》 

年 卷 期：1991年第3卷第2期

页      面：107-119页

主　　题：parallel models of computation parallel algorithms broadcasting with selective reduction maximal sum subsegment 

摘      要：The Broadcasting with Selective Reduction (BSR) model of parallel computation is applied to the problem of finding Maximal Sum Subsegments in one-dimensional sequences of n elements, and to the related problem of Maximal Sum Subrectangles in two-dimensional arrays. The one-dimensional case is shown to be solvable in constant time using O(n) BSR processors. The two-dimensional case is solved in constant time with O(n 3 ) BSR processors (for an n×n array).