We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
PARALLEL ALGORITHMS FOR MAXIMUM SUBSEQUENCE AND MAXIMUM SUBARRAY.
- Authors
PERUMALLA, KALYAN; DEO, NARSINGH
- Abstract
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( 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(n3).
- Publication
Parallel Processing Letters, 1995, Vol 5, Issue 3, p367
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626495000345