This set of Data Structure Problems focuses on “Maximum Sum Rectangle in a 2D Matrix”.
1. Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem?
a) Brute force
b) Recursion
c) Dynamic programming
d) Brute force, Recursion, Dynamic programming
View Answer
Explanation: Brute force, Recursion and Dynamic programming can be used to find the submatrix that has the maximum sum.
2. In which of the following cases, the maximum sum rectangle is the 2D matrix itself?
a) When all the elements are negative
b) When all the elements are positive
c) When some elements are positive and some negative
d) When diagonal elements are positive and rest are negative
View Answer
Explanation: When all the elements of a matrix are positive, the maximum sum rectangle is the 2D matrix itself.
3. Consider the following statements and select which of the following statement are true.
Statement 1: The maximum sum rectangle can be 1X1 matrix containing the largest element If the matrix size is 1X1
Statement 2: The maximum sum rectangle can be 1X1 matrix containing the largest element If all the elements are zero
Statement 3: The maximum sum rectangle can be 1X1 matrix containing the largest element If all the elements are negative
a) Only statement 1 is correct
b) Only statement 1 and Statement 2 are correct
c) Only statement 1 and Statement 3 are correct
d) Statement 1, Statement 2 and Statement 3 are correct
View Answer
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.
4. 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.
a) True
b) False
View Answer
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.
5. Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle?
a) 3
b) 6
c) 12
d) 18
View Answer
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.
6. Consider the 2×2 matrix {{-1,-2},{-3,-4}}. What is the sum of elements of the maximum sum rectangle?
a) 0
b) -1
c) -7
d) -12
View Answer
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.
7. 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?
a) 13
b) 16
c) 14
d) 19
View Answer
Explanation: The complete matrix represents the maximum sum rectangle and it’s sum is 14.
8. What is the time complexity of the brute force implementation of the maximum sum rectangle problem?
a) O(n)
b) O(n2)
c) O(n3)
d) O(n4)
View Answer
Explanation: The time complexity of the brute force implementation of the maximum sum rectangle problem is O(n4).
9. The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm?
a) Hirschberg’s algorithm
b) Needleman-Wunsch algorithm
c) Kadane’s algorithm
d) Wagner Fischer algorithm
View Answer
Explanation: The dynamic programming implementation of the maximum sum rectangle problem uses Kadane’s algorithm.
10. Consider the following code snippet:
int max_sum_rectangle(int arr[][3],int row,int col) { int left, right, tmp[row], mx_sm = INT_MIN, idx, val; for(left = 0; left < col; left++) { for(right = left; right < col; right++) { if(right == left) { for(idx = 0; idx < row; idx++) tmp[idx] = arr[idx][right]; } else { for(idx = 0; idx < row; idx++) tmp[idx] += arr[idx][right]; } val = kadane_algo(tmp,row); if(val > mx_sm) ______; } } return mx_sm; }
Which of the following lines should be inserted to complete the above code?
a) val = mx_sm
b) return val
c) mx_sm = val
d) return mx_sm
View Answer
Explanation: The line “mx_sm = val” should be inserted to complete the above code.
11. What is the time complexity of the following dynamic programming implementation of the maximum sum rectangle problem?
int max_sum_rectangle(int arr[][3],int row,int col) { int left, right, tmp[row], mx_sm = INT_MIN, idx, val; for(left = 0; left < col; left++) { for(right = left; right < col; right++) { if(right == left) { for(idx = 0; idx < row; idx++) tmp[idx] = arr[idx][right]; } else { for(idx = 0; idx < row; idx++) tmp[idx] += arr[idx][right]; } val = kadane_algo(tmp,row); if(val > mx_sm) mx_sm = val; } } return mx_sm; }
a) O(row*col)
b) O(row)
c) O(col)
d) O(row*col*col)
View Answer
Explanation: The time complexity of the above dynamic programming implementation of the maximum sum rectangle is O(row*col*col).
12. What is the space complexity of the following dynamic programming implementation of the maximum sum rectangle problem?
int max_sum_rectangle(int arr[][3],int row,int col) { int left, right, tmp[row], mx_sm = INT_MIN, idx, val; for(left = 0; left < col; left++) { for(right = left; right < col; right++) { if(right == left) { for(idx = 0; idx < row; idx++) tmp[idx] = arr[idx][right]; } else { for(idx = 0; idx < row; idx++) tmp[idx] += arr[idx][right]; } val = kadane_algo(tmp,row); if(val > mx_sm) mx_sm = val; } } return mx_sm; }
a) O(row*col)
b) O(row)
c) O(col)
d) O(row*col*col)
View Answer
Explanation: The space complexity of the above dynamic programming implementation of the maximum sum rectangle problem is O(row).
13. What is the output of the following code?
#include<stdio.h> #include<limits.h> int max_num(int a, int b) { if(a > b) return a; return b; } int kadane_algo(int *arr, int len) { int ans, sum, idx; ans =0; sum =0; for(idx =0; idx < len; idx++) { sum = max_num(0,sum + arr[idx]); ans = max_num(sum,ans); } return ans; } int max_sum_rectangle(int arr[][5],int row,int col) { int left, right, tmp[row], mx_sm = INT_MIN, idx, val; for(left = 0; left < col; left++) { for(right = left; right < col; right++) { if(right == left) { for(idx = 0; idx < row; idx++) tmp[idx] = arr[idx][right]; } else { for(idx = 0; idx < row; idx++) tmp[idx] += arr[idx][right]; } val = kadane_algo(tmp,row); if(val > mx_sm) mx_sm = val; } } return mx_sm; } int main() { int arr[2][5] ={{1, 2, -1, -4, -20}, {-4, -1, 1, 7, -6}}; int row = 2, col = 5; int ans = max_sum_rectangle(arr,row,col); printf("%d",ans); return 0; }
a) 7
b) 8
c) 9
d) 10
View Answer
Explanation: The program prints the sum of elements of the maximum sum rectangle, which is 8.
14. What is the output of the following code?
#include<stdio.h> #include<limits.h> int max_num(int a, int b) { if(a > b) return a; return b; } int kadane_algo(int *arr, int len) { int ans, sum, idx; ans =0; sum =0; for(idx =0; idx < len; idx++) { sum = max_num(0,sum + arr[idx]); ans = max_num(sum,ans); } return ans; } int max_sum_rectangle(int arr[][5],int row,int col) { int left, right, tmp[row], mx_sm = INT_MIN, idx, val=0; for(left = 0; left < col; left++) { for(right = left; right < col; right++) { if(right == left) { for(idx = 0; idx < row; idx++) tmp[idx] = arr[idx][right]; } else { for(idx = 0; idx < row; idx++) tmp[idx] += arr[idx][right]; } val = kadane_algo(tmp,row); if(val > mx_sm) mx_sm = val; } } return mx_sm; } int main() { int arr[4][5] ={{ 7, 1, -3, -6, -15}, { 10, -6, 3, -4, 11}, { -2, -3, -1, 2, -5}, { 3, 0, 1, 0, 3}}; int row = 4, col = 5; int ans = max_sum_rectangle(arr,row,col); printf("%d",ans); return 0; }
a) 17
b) 18
c) 19
d) 20
View Answer
Explanation: The program prints the sum of elements of the maximum sum rectangle, which is 18.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Programming MCQs
- Apply for Computer Science Internship
- Check Programming Books
- Check Design and Analysis of Algorithms Books
- Practice Computer Science MCQs
