1
$\begingroup$

So Kadane's dynamic programming solution for finding the maximum sum contiguous subinterval in a 1-d array runs in linear time, and can be adapted to give a best-known $O(m^2n)$ time solution to find a maximum sum contiguous rectangle in a 2-d array of size $m \times n$. (i.e. find max sum subarray defined by all entries satisfying upper and lower bounds for indices in both dimensions, over all choices of bounds).

However, if the 2-d array is sparse, with $N$ non-zero entries, then the running time can be improved to $O(Nn \log m)$, basically using the same brute force search over choices of start/end rows (or columns) and updating the optimal solution for each choice of start/end rows by storing the optimal solution of start/end columns for every contiguous subset of columns defined by sets of contiguous columns being repeatedly split in half into two contiguous sets of half as many columns, in a binary tree fashion, and some auxilary information is stored at each node in the tree, besides just the optimal solution of start/end column, like the optimal solution that ends at the rightmost column in the subset, or begins at the leftmost column. Then, when a new non-zero entry is added, the optimal solution and additional information is propagated from the leaf column to the root (representing the optimal solution over all columns), in constant time per propagation step, so overall $O(\log m)$ time.

Anyway, I would like to find a similarly good speed up for finding the maximum AVERAGE value contiguous 2-d subarray in a $m \times n$ array with $N$ non-zero entries. Obviously average value can be maximized by one single element in the array that has maximum value, so we put a lower bound of requiring at least $K$ cells in the subarray before finding maximum average. In terms of $m,n,N,K$, can a fast algorithm be found to solve this, i.e. faster than just assuming the input array is dense?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.