Maximum contiguous submatrix
Find the contiguous 2dimensional submatrix with the maximum sum, in a given 2 dimensional matrix of n elements of signed integer type.
Problem Statement
Given an Ndimensional matrix of n elements of signed integer type, find the contiguous submatrix with the maximum sum.
Simplified version: Given a 2 dimensional matrix of n elements of signed integer type, find the contiguous 2dimensional submatrix with the maximum sum (see example figure).
Trivia: The simplified 1dimensional 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 pseudocode 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 KMaximum 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.
Recommended reading

Fibonacci Series Dynamic Programming
Return the Nth element of the Fibonacci series (1, 1, 2, 3, 5, 8, 13, 21, ...) efficiently without using any FOR or WHILE loops.

Time Complexity of ArrayList Insertion
Then calculate the average time complexity of inserting n new items into an empty brand new ArrayList.

Return true if input is a Prime number
You are given n, a positive integer. Return true if n is a prime number, and false if it's not.
 Author
 Amin Ariana
 Published
 February 2011