Sub-cubic Time Algorithm for the k-disjoint Maximum subarray Problem (2011)
Type of ContentTheses / Dissertations
Thesis DisciplineComputer Science
Degree NameMaster of Science
PublisherUniversity of Canterbury. Computer Science and Software Engineering
AuthorsLee, Sang Myung (Chris)show all
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.
KeywordsMaximum Subarray Problem, Distance Matrix Multiplication, k-maximum Subarray Problem, k-disjoint Maximum Subarray Problem, Table-Lookup, X+Y Problem
RightsCopyright Sang Myung (Chris) Lee
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 ...
Sustainable Problems of Development: Does the EU contribute to the sustainable development of Tonga? Reichstein, Andrea (University of Canterbury. National Centre for Research on Europe, 2008)Sustainable development increasingly provides new norms in the international agenda for development assistance. As an international development actor the European Union (EU) integrates this notion into its objectives ...