Data Structure

Maximum Sum Rectangle in a 2D Matrix

Question 1
Marks : +2 | -2
Pass Ratio : 100%
Consider the following code snippet:
Explanation:
Question 2
Marks : +2 | -2
Pass Ratio : 100%
The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm?
Hirschberg’s algorithm
Needleman-Wunsch algorithm
Kadane’s algorithm
Wagner Fischer algorithm
Explanation:
The dynamic programming implementation of the maximum sum rectangle problem uses Kadane’s algorithm.
Question 3
Marks : +2 | -2
Pass Ratio : 100%
Consider the following statements and select which of the following statement are true.
Only statement 1 is correct
Only statement 1 and Statement 2 are correct
Only statement 1 and Statement 3 are correct
Statement 1, Statement 2 and Statement 3 are correct
Explanation:
If the matrix size is 1×1 then the element itself is the maximum sum of that 1×1 matrix. If all elements are zero, then the sum of any submatrix of the given matrix is zero. If all elements are negative, then the maximum element in that matrix is the highest sum in that matrix which is again 1X1 submatrix of the given matrix. Hence all three statements are correct.
Question 4
Marks : +2 | -2
Pass Ratio : 100%
Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle?
3
6
12
18
Explanation:
Since all the elements of the 2×3 matrix are positive, the maximum sum rectangle is the matrix itself and the sum of elements is 12.
Question 5
Marks : +2 | -2
Pass Ratio : 100%
Consider the 2×2 matrix {{-1,-2},{-3,-4}}. What is the sum of elements of the maximum sum rectangle?
0
-1
-7
-12
Explanation:
Since all the elements of the 2×2 matrix are negative, the maximum sum rectangle is {-1}, a 1×1 matrix containing the largest element. The sum of elements of the maximum sum rectangle is -1.
Question 6
Marks : +2 | -2
Pass Ratio : 100%
In which of the following cases, the maximum sum rectangle is the 2D matrix itself?
When all the elements are negative
When all the elements are positive
When some elements are positive and some negative
When diagonal elements are positive and rest are negative
Explanation:
When all the elements of a matrix are positive, the maximum sum rectangle is the 2D matrix itself.
Question 7
Marks : +2 | -2
Pass Ratio : 100%
Consider the 3×3 matrix {{2,1,-3},{6,3,4},{-2,3,0}}. What is the sum of the elements of the maximum sum rectangle?
13
16
14
19
Explanation:
The complete matrix represents the maximum sum rectangle and it’s sum is 14.
Question 8
Marks : +2 | -2
Pass Ratio : 100%
Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem?
Brute force
Recursion
Dynamic programming
Brute force, Recursion, Dynamic programming
Explanation:
Brute force, Recursion and Dynamic programming can be used to find the submatrix that has the maximum sum.
Question 9
Marks : +2 | -2
Pass Ratio : 100%
Consider a matrix in which all the elements are non-zero(at least one positive and at least one negative element). In this case, the sum of the elements of the maximum sum rectangle cannot be zero.
True
False
Explanation:
If a matrix contains all non-zero elements with at least one positive and at least on negative element, then the sum of elements of the maximum sum rectangle cannot be zero.
Question 10
Marks : +2 | -2
Pass Ratio : 100%
What is the time complexity of the brute force implementation of the maximum sum rectangle problem?
O(n)
O(n2)
O(n3)
O(n4)
Explanation:
The time complexity of the brute force implementation of the maximum sum rectangle problem is O(n4).