Bae, Sung EunTakaoka, T.2009-10-262009-10-262006Bae, S.E., Takaoka, T. (2006) Ranking Cartesian Sums and K-maximum subarrays. 9pp.http://hdl.handle.net/10092/3020TR-COSC 03/08We 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.enCartesian sumsK-maximum subarraysReportsFields of Research::280000 Information, Computing and Communication SciencesFields of Research::280000 Information, Computing and Communication Sciences::280400 Computation Theory and Mathematics::280401 Analysis of algorithms and complexity