Data Structure MCQs on “Maximum Sum of Continuous Subarray – 2”.
1. Which line should be inserted in the blank to complete the following dynamic programming implementation of the maximum sub-array sum problem?
#includeint max_num(int a,int b) { if(a> b) return a; return b; } int maximum_subarray_sum(int *arr, int len) { int sum[len], idx; sum[0] = arr[0]; for(idx = 1; idx < len; idx++) sum[idx] = _______________________; int mx = sum[0]; for(idx = 0; idx < len; idx++) if(sum[idx] > mx) mx =sum[idx]; return mx; } int main() { int arr[] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9; int ans = maximum_subarray_sum(arr, len); printf("%d",ans); return 0; }
a) max_num(sum[idx – 1] + arr[idx], arr[idx]) Answer: a 2. What is the time complexity of the following dynamic programming algorithm used to find the maximum sub-array sum? a) O(n) Answer: a 3. What is the space complexity of the following dynamic programming algorithm used to find the maximum sub-array sum? a) O(n) Answer: a 4. Consider the following code snippet. Which property is shown by line 4 of the below code snippet? a) Optimal substructure Answer: a 5. Consider the following code snippet: Which method is used by line 4 of the above code snippet? Answer: d 6. Find the maximum sub-array sum for the following array: Answer: b 7. What is the output of the following program? a) 27 Answer: b 8. What is the value stored in sum[4] after the following program is executed? a) 28 Answer: c
b) sum[idx – 1] + arr[idx].
c) min_num(sum[idx – 1] + arr[idx], arr[idx])
d) arr[idx].
Clarification: The array “sum” is used to store the maximum sub-array sum. The appropriate way to do this is by using:
sum[idx] = max_num(sum[idx – 1] + arr[idx], arr[idx]).#include
b) O(logn)
c) O(nlogn)
d) O(n2)
View Answer
Clarification: The time complexity of the above dynamic programming algorithm used to solve maximum sub-array sum is O(n).#include
b) O(1)
c) O(n!)
d) O(n2)
Clarification: The above dynamic programming algorithm uses space equal to the length of the array to store the sum values. So, the space complexity is O(n).1. int sum[len], idx;
2. sum[0] = arr[0];
3. for(idx = 1; idx < len; idx++)
4. sum[idx] = max(sum[idx - 1] + arr[idx], arr[idx]);
5. int mx = sum[0];
6. for(idx = 0; idx < len; idx++)
7. if(sum[idx] > mx)
8. mx =sum[idx];
9. return mx;
b) Overlapping subproblems
c) Both overlapping subproblems and optimal substructure
d) Greedy substructure
Clarification: The current sum (i.e. sum[idx]) uses the previous sum (i.e. sum[idx – 1]) to get an optimal value. So, line 4 shows the optimal substructure property.1. int sum[len], idx;
2. sum[0] = arr[0];
3. for(idx = 1; idx < len; idx++)
4. sum[idx] = max(sum[idx - 1] + arr[idx], arr[idx]);
5. int mx = sum[0];
6. for(idx = 0; idx < len; idx++)
7. if(sum[idx] > mx)
8. mx =sum[idx];
9. return mx;
a) Divide and conquer
b) Recursion
c) Both memoization and divide and conquer
d) Memoization
Clarification: The array “sum” is used to store the previously calculated values, so that they aren’t recalculated. So, line 4 uses the memoization technique.
{3, 6, 7, 9, 3, 8}
a) 33
b) 36
c) 23
d) 26
Clarification: 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.#include
b) 37
c) 36
d) 26
Clarification: The program prints the value of maximum sub-array sum, which is 37.#include
b) 25
c) 22
d) 12
Clarification: After the program is executed the value stored in sum[4] is 22.
Note: You are asked to find the value stored in sum[4] and NOT the output of the program.