Computer Science and
     Software Engineering

Computer Science and Software Engineering

TR-COSC 03/06

Ranking Cartesian Sums and K -maximum subarray problem

Sung Eun Bae and Tadao Takaoka
Department of Computer Science
University of Canterbury

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.