This set of Data Structure MCQs focuses 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?
#include<stdio.h> int 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])
b) sum[idx – 1] + arr[idx].
c) min_num(sum[idx – 1] + arr[idx], arr[idx])
d) arr[idx].
View Answer
Explanation: 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]).
2. What is the time complexity of the following dynamic programming algorithm used to find the maximum sub-array sum?
#include<stdio.h> int 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] = max_num(sum[idx - 1] + arr[idx], arr[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) O(n)
b) O(logn)
c) O(nlogn)
d) O(n2)
View Answer
Explanation: The time complexity of the above dynamic programming algorithm used to solve maximum sub-array sum is O(n).
3. What is the space complexity of the following dynamic programming algorithm used to find the maximum sub-array sum?
#include<stdio.h> int 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] = max_num(sum[idx - 1] + arr[idx], arr[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) O(n)
b) O(1)
c) O(n!)
d) O(n2)
View Answer
Explanation: 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).
4. Consider the following code snippet. Which property is shown by line 4 of the below code snippet?
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) Optimal substructure
b) Overlapping subproblems
c) Both overlapping subproblems and optimal substructure
d) Greedy substructure
View Answer
Explanation: 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.
5. Consider the following code snippet:
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;
Which method is used by line 4 of the above code snippet?
a) Divide and conquer
b) Recursion
c) Both memoization and divide and conquer
d) Memoization
View Answer
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.
6. Find the maximum sub-array sum for the following array:
{3, 6, 7, 9, 3, 8}
a) 33
b) 36
c) 23
d) 26
View Answer
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.
7. What is the output of the following program?
#include<stdio.h> int 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] = max_num(sum[idx - 1] + arr[idx], arr[idx]); int mx = sum[0]; for(idx = 0; idx < len; idx++) if(sum[idx] > mx) mx =sum[idx]; return mx; } int main() { int arr[] = {-20, 23, 10, 3, -10, 11, -5},len = 7; int ans = maximum_subarray_sum(arr, len); printf("%d",ans); return 0; }
a) 27
b) 37
c) 36
d) 26
View Answer
Explanation: The program prints the value of maximum sub-array sum, which is 37.
8. What is the value stored in sum[4] after the following program is executed?
#include<stdio.h> int 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] = max_num(sum[idx - 1] + arr[idx], arr[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, 14, 11, -13, 10, -5, 11, -6, 3, -5},len = 10; int ans = maximum_subarray_sum(arr, len); printf("%d",ans); return 0; }
a) 28
b) 25
c) 22
d) 12
View Answer
Explanation: 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.
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.
- Practice Data Structure MCQ
- Check Computer Science Books
- Check Programming Books
- Check Design and Analysis of Algorithms Books
- Practice Computer Science MCQs
