Ranking Cartesian Sums and K-maximum subarrays
Type of content
Reports
UC permalink
Publisher's DOI/URI
Thesis discipline
Degree name
Publisher
Department of Computer Science and Software Engineering, University of Canterbury
University of Canterbury. Computer Science and Software Engineering
University of Canterbury. Computer Science and Software Engineering
Journal Title
Journal ISSN
Volume Title
Language
Date
2006
Authors
Bae, Sung Eun
Takaoka, T.
Abstract
We design a simple algorithm that ranks K largest in Cartesian sums X + Y in O(m + K logK) time. Based on this, K-maximum subarrays can be computed in O(n+K logK) time (1D) and O(n3 +K logK) time (2D) for input array of size n and n × n respectively.
Description
TR-COSC 03/08
Citation
Bae, S.E., Takaoka, T. (2006) Ranking Cartesian Sums and K-maximum subarrays. 9pp.
Keywords
Cartesian sums, K-maximum subarrays