Skip Navigation

The Computer Journal 2006 49(3):358-374; doi:10.1093/comjnl/bxl007
This Article
Right arrow Full Text
Right arrow Full Text (PDF)
Right arrow Corrigendum
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (2)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Bae, S. E.
Right arrow Articles by Takaoka, T.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2006. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Improved Algorithms for the K-Maximum Subarray Problem

Sung Eun Bae* and Tadao Takaoka

Department of Computer Science and Software Engineering, University of Canterbury Christchurch, New Zealand

*Corresponding author: seb43{at}student.canterbury.ac.nz

The maximum subarray problem is to find the contiguous array elements having the largest possible sum. We extend this problem to find K maximum subarrays. For general K maximum subarrays where overlapping is allowed, Bengtsson and Chen presented Formula time algorithm for one-dimensional case, which finds unsorted subarrays. Our algorithm finds K maximum subarrays in sorted order with improved complexity of O ((n + K) log K). For the two-dimensional case, we introduce two techniques that establish O(n3) and subcubic time.

Key Words: Maximum subarray • persistent 2-3 tree • selection in matrices with sorted columns • distance matrix multiplication


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.