Ranking Cartesian Sums and K -maximum subarray problem
Degree GrantorUniversity of Canterbury
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.
- Engineering: Reports