How to catch gold fish using the maximum subarray algorithm

Tadao Takaoka

Dept of CSSE, University of Canterbury

Fri Jul 30 15:10:00 NZST 2004 in Room 031, MSCS

Abstract

There are two factors in catching many gold fish with a paper spoon.

1. Locate the best spot that can maximize the number of gold fish
2. Great skill, which includes quick movement of the paper spoon underneath goldfish and scoop them in the up-horizontal direction to scoop only goldfish without scooping water.

As the paper spoon breaks very quickly once in the water, time is crucial. I am not good in (2), but good in (1) with my algorithm for maximum subarray.

In this talk, I describe an algorithm for finding a rectangular subarray with the maximum sum in the given (n,n) array, whose running time is O(n^3loglogn/logn). I also describe an algorithm for the k maximum subarrays with O(kn^3loglogn/logn) time.

The maximum subarray problem is a fundamental technique in data mining and graphics. In data mining, we can identify the most promising customer range, whereas in graphics, we can find the brightest spot in the image. The k-maximum subarray problem can identify the second, third, etc., promising portion, when the first is not suitable for some reason.