• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

find sub-matrix with the maximum sum

 
Ranch Hand
Posts: 206
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
given N x N matrix of positive and negetive intergers. Write some code
that finds the sub-matrix with teh maximum sum of its elements.

Any ideas?


Thanks
 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
There's an obvious O(N^6) brute force algorithm.

For each combination of upper left and lower right corners { // O(N^4)
Calculate the sum; // O(N^2)
If the new sum is greater than old maximum, remember it.
}

A question very similar to this in one dimension has an O(N) solution. That makes me think there must be an O(N^2) one for this.
[ October 15, 2007: Message edited by: Ryan McGuire ]
 
reply
    Bookmark Topic Watch Topic
  • New Topic