Sub-cubic Time Algorithm for the k-disjoint Maximum subarray Problem
Thesis DisciplineComputer Science
Degree GrantorUniversity of Canterbury
Degree NameMaster of Science
The maximum subarray problem is to find the array portion that maximizes the sum of array elements in it. This problem was first introduced by Grenander and brought to computer science by Bentley in 1984. This problem has been branched out into other problems based on their characteristics. k-overlapping maximum subarray problem where the overlapping solutions are allowed, and k-disjoint maximum subarray problem where all the solutions are disjoint from each other are those. For k-overlapping maximum subarray problems, significant improvement have been made since the problem was first introduced. For k-disjoint maximum subarrsy, Ruzzo and Tompa gave an O(n) time solution for one-dimension. This solution is, however, difficult to extend to two-dimensions. While a trivial solution of O(kn^3) time is easily obtainable for two-dimensions, little study has been undertaken to better this. This paper introduces a faster algorithm for the k-disjoint maximum sub-array problem under the conventional RAM model, based on distance matrix multiplication. Also, DMM reuse technique is introduced for the maximum subarray problem based on recursion for space optimization.
SubjectsMaximum Subarray Problem, Distance Matrix Multiplication, k-maximum Subarray Problem, k-disjoint Maximum Subarray Problem, Table-Lookup, X+Y Problem
Showing items related by title, author, creator and subject.
A study of the problems of adjustment faced by a group of Hong Kong orphans adopted into New Zealand families : with an investigation into possible problems of school and later life. Brash, Eljean Ivory (University of Canterbury. School of Educational Studies and Human Development, 1963)The purpose of this study was to discover how far orphan children, of a race other than European, would, if adopted into New Zealand-European homes, be likely to adjust to, and benefit from, a permanent life in New ...
Creating and Evaluating Problem Templates for Problem Generation Within the Context of Stroke Cognitive Rehabilitation Ogden, Scott (University of Canterbury, 2012)Stroke Rehabilitation would be more effective if the patients conducted activities personalised to them, as opposed to a set of generic activities which may be irrelevant. This project has the intention of creating problem ...
Culpan, I. (University of Canterbury. School of Sport &Physical Education, 2015)Physical education, sport and everyday living, no matter in which cultural context, has at its centrality physical activity. The concept of movement, whether one understands it as a social construct or originating from an ...