ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
8 practice sets · Page 1 of 1
Find the maximum sub-array sum for the following array: {3, 6, 7, 9, 3, 8}
33
36
23
26
All the elements of the array are positive. So, the maximum sub-array sum is equal to the sum of all the elements, which is 36.
Which method is used by line 4 of the above code snippet?
Divide and conquer
Recursion
Both memoization and divide and conquer
Memoization
The array "sum" is used to store the previously calculated values, so that they aren't recalculated. So, line 4 uses the memoization technique.
What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
O(n)
O(1)
O(n!)
O(n^{2})
The divide and conquer algorithm uses a constant space. So, the space complexity is O(1).
What is the time complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
O(n)
O(logn)
O(nlogn)
O(n^{2})
The time complexity of the divide and conquer algorithm used to find the maximum sub-array sum is O(nlogn).
Which line should be inserted to complete the above code?
(tmp_max = cur_max)
break
continue
(cur_max = tmp_max)
If the tmp_max element is greater than the cur_max element, we make cur_max equal to tmp_max, i.e. (cur_max = tmp_max).
Find the maximum sub-array sum for the given elements. {-2, -1, -3, -4, -1, -2, -1, -5, -4}
-3
5
3
-1
All the elements are negative. So, the maximum sub-array sum will be equal to the largest element. The largest element is -1 and therefore, the maximum sub-array sum is -1.
Find the maximum sub-array sum for the given elements. {2, -1, 3, -4, 1, -2, -1, 5, -4}
3
5
8
6
The maximum sub-array sum is 5.
Given a one-dimensional array of integers, you have to find a sub-array with maximum sum. This is the maximum sub-array sum problem. Which of these methods can be used to solve the problem?
Dynamic programming
Two for loops (naive method)
Divide and conquer
Dynamic programming, naïve method and Divide and conquer methods
Dynamic programming, naïve method and Divide and conquer methods can be used to solve the maximum sub array sum problem.
