Ranking Cartesian Sums and K -maximum subarray problem
Type of content
Theses / Dissertations
UC permalink
Publisher's DOI/URI
Thesis discipline
Degree name
Other
Publisher
University of Canterbury
Journal Title
Journal ISSN
Volume Title
Language
English
Date
2006
Authors
Bae, Sung Eun
Takaoka, Tadao
Abstract
We design a simple algorithm that ranks K largest in Cartesian sums X + Y in O(m + K log K ) time. Based on this, K -maximum subarrays can be computed in O(n + K log K ) time (1D) and O(n3 + K log K ) time (2D) for input array of size n and n × n respectively.
Description
Citation
Keywords
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Rights
All Right Reserved