Win a copy of Five Lines of Code this week in the OO, Patterns, UML and Refactoring forum!
  • 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Liutauras Vilda
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • fred rosenberger
  • salvin francis
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Carey Brown

find sub-matrix with the maximum sum

 
Ranch Hand
Posts: 206
  • Mark post as helpful
  • send pies
  • 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
 
Rancher
Posts: 1197
22
  • Mark post as helpful
  • send pies
  • 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 ]
 
Consider Paul's rocket mass heater.
    Bookmark Topic Watch Topic
  • New Topic