Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #6701
| Path | csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail |
|---|---|
| From | Daniel Pitts <usenet@coloraura.com> |
| Newsgroups | comp.programming |
| Subject | Re: A faster maximal partial sum in a rectangle. |
| Date | Fri, 8 Jul 2016 08:43:11 -0700 |
| Organization | A noiseless patient Spider |
| Lines | 18 |
| Message-ID | <nlohmg$d8a$1@dont-email.me> (permalink) |
| References | <f70420a7-6d08-4735-9c20-97c66e90b732@googlegroups.com> |
| Mime-Version | 1.0 |
| Content-Type | text/plain; charset=utf-8; format=flowed |
| Content-Transfer-Encoding | 7bit |
| Injection-Date | Fri, 8 Jul 2016 15:43:12 -0000 (UTC) |
| Injection-Info | mx02.eternal-september.org; posting-host="cbfa5976b011f5e32250391c9021fef7"; logging-data="13578"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+ztS02YVOD1vUbjmAS95EheRNjtsHbW+o=" |
| User-Agent | Mozilla/5.0 (Macintosh; Intel Mac OS X 10.10; rv:45.0) Gecko/20100101 Thunderbird/45.1.1 |
| In-Reply-To | <f70420a7-6d08-4735-9c20-97c66e90b732@googlegroups.com> |
| Cancel-Lock | sha1:2pArY18cQV9V0yEAK1J+EViOKDQ= |
| Xref | csiph.com comp.programming:6701 |
Show key headers only | 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
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