hard20 pts · first answer countsarrayskadanematrix

Maximum sum rectangle in a matrix

To find the rectangle with the largest sum in an r × c matrix, a common method fixes a pair of rows and compresses the columns between them. Which method then finishes the job, and at what total cost?

A.Binary search on the column sums, O(r × c log c)B.Sorting the column sums, O(r × c log c)C.Kadane on each row alone, O(r × c)D.Kadane on the column sums, O(r² × c)

Discussion 0

Join free to post in the discussion.

Maximum sum rectangle in a matrix

Discussion 0

Related questions