Maximum Value Contiguous Subregion

0 votes

You are given a two dimentional array A[1:n, 1..n] of real numbers (possibly containing both positive and negative real numbers)You want to find a rectangular sub-region of the array that maximizes the sum of that region.  For example, the subarray S(1,2,5,8) consists of contiguous rectangle between A[1,2] to A[5,8], both corners inclusive, therefore, it has 35 total numbers.

Give the most efficient algorithm for this problem that you can.

asked Jul 23 in Dynamic Programming by Amrinder Arora (38 points)

Please log in or register to answer this question.

The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc