Maximum contiguous sub-matrix

posted Feb 4, 2011 5:24 PM by Amin Ariana   [ updated Feb 4, 2011 5:53 PM ]
Tags: Moderate, dynamic programming

Problem description

Given an N-dimensional matrix of n elements of signed integer type, find the contiguous sub-matrix with the maximum sum.

Simplified version: Given a 2 dimensional matrix of n elements of signed integer type, find the contiguous 2-dimensional sub-matrix with the maximum sum (see example figure).

The simplified 1-dimensional array version of this problem was first posed in 1977 as a simplified model for maximum likelihood estimation of patterns in digitized images.

Grading
  • Completeness of the C# or pseudo-code algorithm (25%)
  • Correctness of the algorithm, demonstrated by quick manual unit tests (25%)
  • What is the time and space complexity of your algorithm? (25%)
  • Is the most efficient solution offered? (25%)

References

Norman, a fellow engineer at Adify, asked me this question during a seven hour final round interview.

Maximum subarray problem. Wikipedia. http://en.wikipedia.org/wiki/Maximum_subarray_problem (accessed Feb. 2011)

Improved Algorithms for the K-Maximum Subarray problem. Oxford Journals. http://comjnl.oxfordjournals.org/content/49/3/358.full (accessed Feb. 2011)

Sign in|Report Abuse|Print Page|Remove Access|Powered By Google Sites