Suppose we have a d-dimensional array A (d > 1) where each dimension has length n. The array is given in sparse notation as input, and the number of given non-zero elements is N. We want to find a contiguous range of indices for each dimension such that the sum of entries in the arising subarray "box" is maximized. For d=2 there is an O(N n log n) algorithm that is a modification of Kadane's O(n^3) original algorithm for a dense square array. However this sparse d=2 algorithm still requires a brute force search over ranges of rows, and straightforward extensions of the algorithm to higher dimensional arrays seem to be exponential complexity if the dimension d is not fixed.

So is it an NP-hard problem when d is not fixed? I'm particularly interested in the case where N = n, and each d-1 dimensional "flat" (fix one index in one dimension, and let all other indices vary between 1 and n) has exactly one non-zero element (a generalization of a product of a diagonal matrix and permutation matrix for the case d=2). Maybe this case is NP-hard? But the general case of a sparsely presented array is also of interest. Note this includes the case N=n^d, i.e. a dense array, but I'm wondering if the running time can be given in terms of N like the d=2 case, so that the running time can potentially be reduced when the array is sparse. Even if the problem is NP-hard for some N, I'd still be interested to find algorithms as efficient as possible, e.g. in terms of N. But the N=n case I described is the most important to me.


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.