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.
| Identifer | oai:union.ndltd.org:canterbury.ac.nz/oai:ir.canterbury.ac.nz:10092/6494 |
| Date | January 2011 |
| Creators | Lee, Sang Myung (Chris) |
| Publisher | University of Canterbury. Computer Science and Software Engineering |
| Source Sets | University of Canterbury |
| Language | English |
| Detected Language | English |
| Type | Electronic thesis or dissertation, Text |
| Rights | Copyright Sang Myung (Chris) Lee, http://library.canterbury.ac.nz/thesis/etheses_copyright.shtml |
| Relation | NZCU |
Page generated in 0.0019 seconds