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
Correct Answer: B — 36
Explanation:
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
Correct Answer: D — Memoization
Explanation:
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})
Correct Answer: B — O(1)
Explanation:
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})
Correct Answer: C — O(nlogn)
Explanation:
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)
Correct Answer: D — (cur_max = tmp_max)
Explanation:
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
Correct Answer: D — -1
Explanation:
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
Correct Answer: B — 5
Explanation:
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
Correct Answer: D — Dynamic programming, naïve method and Divide and conquer methods
Explanation:
Dynamic programming, naïve method and Divide and conquer methods can be used to solve the maximum sub array sum problem.
