10 practice sets · Page 1 of 1
Which of the following lines should be inserted to complete the above code?
val = mx_sm
return val
mx_sm = val
return mx_sm
Correct Answer: C — mx_sm = val
Explanation:
The line "mx_sm = val" should be inserted to complete the above code.
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
Correct Answer: C — Kadane's algorithm
Explanation:
The dynamic programming implementation of the maximum sum rectangle problem uses Kadane's algorithm.
What is the time complexity of the brute force implementation of the maximum sum rectangle problem?
O(n)
O(n^{2})
O(n^{3})
O(n^{4})
Correct Answer: D — O(n^{4})
Explanation:
The time complexity of the brute force implementation of the maximum sum rectangle problem is O(n^{4}).
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
Correct Answer: C — 14
Explanation:
The complete matrix represents the maximum sum rectangle and it's sum is 14.
Consider the 2×2 matrix {{-1,-2},{-3,-4}}. What is the sum of elements of the maximum sum rectangle?
0
-1
-7
-12
Correct Answer: B — -1
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.
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
Correct Answer: C — 12
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.
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
Correct Answer: A — True
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.
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
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
Correct Answer: D — 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.
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
Correct Answer: A — When all the elements are negative
Explanation:
When all the elements of a matrix are positive, the maximum sum rectangle is the 2D matrix itself.
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
Correct Answer: D — Brute force, Recursion, Dynamic programming
Explanation:
Brute force, Recursion and Dynamic programming can be used to find the submatrix that has the maximum sum.
