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

Groups > comp.programming > #6701

Re: A faster maximal partial sum in a rectangle.

Show all headers | View raw

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.

Back to comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

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

csiph-web