Data Structure Questions and Answers – Maximum Sum Rectangle in a 2D Matrix

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

Answer: d
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

Answer: a
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

Answer: d
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.

advertisement
advertisement

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

Answer: a
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

Answer: c
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

Answer: b
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

Answer: c
Explanation: The complete matrix represents the maximum sum rectangle and it’s sum is 14.
advertisement

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

Answer: d
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

Answer: c
Explanation: The dynamic programming implementation of the maximum sum rectangle problem uses Kadane’s algorithm.
advertisement

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

Answer: c
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

Answer: d
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

Answer: b
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

Answer: b
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

Answer: b
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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.