Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #6700 > unrolled thread

A faster maximal partial sum in a rectangle.

Back to article view | Back to comp.programming

Contents

  A faster maximal partial sum in a rectangle. Paul <pepstein5@gmail.com> - 2016-07-08 03:53 -0700
    Re: A faster maximal partial sum in a rectangle. Daniel Pitts <usenet@coloraura.com> - 2016-07-08 08:43 -0700

#6700 — A faster maximal partial sum in a rectangle.

A rectangular matrix is filled with positive and negative numbers.  Please consider the problem of finding the maximal sum over any subrectangle.  (And if you don't want to consider this problem, I don't see why you're reading this post in the first place.)

Let n be the maximum length of any edge.  O(n ^ 3) solutions are well-known but is there an O(n ^ 2) solution?  If not, does anyone know of a proof that no such solution exists.

Many thanks.

Paul Epstein

[toc] | [next] | [standalone]

#6701

On 7/8/16 3:53 AM, Paul wrote:
> A rectangular matrix is filled with positive and negative numbers.  Please consider the problem of finding the maximal sum over any subrectangle.  (And if you don't want to consider this problem, I don't see why you're reading this post in the first place.)
>
> Let n be the maximum length of any edge.  O(n ^ 3) solutions are well-known but is there an O(n ^ 2) solution?  If not, does anyone know of a proof that no such solution exists.
>
> Many thanks.
>
> Paul Epstein
>

This sounds like a Dynamic Programming solution would reduce the 
complexity, but I was never very good at determining a DP solution to 
any given problem.

You could probably get some reduction in cost by precomputing runs of 
various lengths, or using memoization to reduce duplicated computations, 
though I don't think that reduces the Big O.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web