Illustration

Maximum contiguous sub-matrix

Find the contiguous 2-dimensional sub-matrix with the maximum sum, in a given 2 dimensional matrix of n elements of signed integer type.


Problem Statement

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).

Trivia: 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.


Evaluation


  • Completeness of the 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%)


See also

Maximum subarray problem . Wikipedia (accessed Feb. 2011)
Improved Algorithms for the K-Maximum Subarray problem . Oxford Journals (accessed Feb. 2011)


References

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

Amin A.

Written by

Amin Ariana

A software entrepreneur from San Francisco