This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Kadane’s Algorithm”.
1. Kadane’s algorithm is used to find ____________
a) Longest increasing subsequence
b) Longest palindrome subsequence
c) Maximum sub-array sum
d) Longest decreasing subsequence
View Answer
Explanation: Kadane’s algorithm is used to find the maximum sub-array sum for a given array.
2. Kadane’s algorithm uses which of the following techniques?
a) Divide and conquer
b) Dynamic programming
c) Recursion
d) Greedy algorithm
View Answer
Explanation: Kadane’s algorithm uses dynamic programming.
3. For which of the following inputs would Kadane’s algorithm produce the INCORRECT output?
a) {0,1,2,3}
b) {-1,0,1}
c) {-1,-2,-3,0}
d) {-4,-3,-2,-1}
View Answer
Explanation: Kadane’s algorithm works if the input array contains at least one non-negative element. Every element in the array {-4,-3,-2,-1} is negative. Hence Kadane’s algorithm won’t work.
4. For which of the following inputs would Kadane’s algorithm produce a WRONG output?
a) {1,0,-1}
b) {-1,-2,-3}
c) {1,2,3}
d) {0,0,0}
View Answer
Explanation: Kadane’s algorithm doesn’t work for all negative numbers. So, the answer is {-1,-2,-3}.
5. Complete the following code for Kadane’s algorithm:
#include<stdio.h> int max_num(int a, int b) { if(a > b) return a; return b; } int kadane_algo(int *arr, int len) { int ans, sum, idx; ans =0; sum =0; for(idx =0; idx < len; idx++) { sum = max_num(0,sum + arr[idx]); ans = ___________; } return ans; } int main() { int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3},len=7; int ans = kadane_algo(arr,len); printf("%d",ans); return 0; }
a) max_num(sum, sum + arr[idx])
b) sum
c) sum + arr[idx]
d) max_num(sum,ans)
View Answer
Explanation: The maximum of sum and ans, is stored in ans. So, the answer is max_num(sum, ans).
6. What is the time complexity of Kadane’s algorithm?
a) O(1)
b) O(n)
c) O(n2)
d) O(5)
View Answer
Explanation: The time complexity of Kadane’s algorithm is O(n) because there is only one for loop which scans the entire array exactly once.
7. What is the space complexity of Kadane’s algorithm?
a) O(1)
b) O(n)
c) O(n2)
d) None of the mentioned
View Answer
Explanation: Kadane’s algorithm uses a constant space. So, the space complexity is O(1).
8. What is the output of the following implementation of Kadane’s algorithm?
#include<stdio.h> int max_num(int a, int b) { if(a > b) return a; return b; } int kadane_algo(int *arr, int len) { int ans, sum, idx; ans =0; sum =0; for(idx =0; idx < len; idx++) { sum = max_num(0,sum + arr[idx]); ans = max_num(sum,ans); } return ans; } int main() { int arr[] = {2, 3, -3, -1, 2, 1, 5, -3}, len = 8; int ans = kadane_algo(arr,len); printf("%d",ans); return 0; }
a) 6
b) 7
c) 8
d) 9
View Answer
Explanation: Kadane’s algorithm produces the maximum sub-array sum, which is equal to 9.
9. What is the output of the following implementation of Kadane’s algorithm?
#include<stdio.h> int max_num(int a, int b) { if(a > b) return a; return b; } int kadane_algo(int *arr, int len) { int ans, sum, idx; ans =0; sum =0; for(idx =0; idx < len; idx++) { sum = max_num(0,sum + arr[idx]); ans = max_num(sum,ans); } return ans; } int main() { int arr[] = {-2, -3, -3, -1, -2, -1, -5, -3},len = 8; int ans = kadane_algo(arr,len); printf("%d",ans); return 0; }
a) 1
b) -1
c) -2
d) 0
View Answer
Explanation: Kadane’s algorithm produces a wrong output when all the elements are negative. The output produced is 0.
10. Consider the following implementation of Kadane’s algorithm:
1. #include<stdio.h> 2. int max_num(int a, int b) 3. { 4. if(a > b) 5. return a; 6. return b; 7. } 8. int kadane_algo(int *arr, int len) 9. { 10. int ans = 0, sum = 0, idx; 11. for(idx =0; idx < len; idx++) 12. { 13. sum = max_num(0,sum + arr[idx]); 14. ans = max_num(sum,ans); 15. } 16. return ans; 17. } 18. int main() 19. { 20. int arr[] = {-2, -3, -3, -1, -2, -1, -5, -3},len = 8; 21. int ans = kadane_algo(arr,len); 22. printf("%d",ans); 23. return 0; 24. }
What changes should be made to the Kadane’s algorithm so that it produces the right output even when all array elements are negative?
Change 1 = Line 10: int sum = arr[0], ans = arr[0] Change 2 = Line 13: sum = max_num(arr[idx],sum+arr[idx])
a) Only Change 1 is sufficient
b) Only Change 2 is sufficient
c) Both Change 1 and Change 2 are necessary
d) No change is required
View Answer
Explanation: Both change 1 and change 2 should be made to Kadane’s algorithm so that it produces the right output even when all the array elements are negative.
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.
- Check Computer Science Books
- Practice Data Structure MCQ
- Check Programming Books
- Practice Computer Science MCQs
- Apply for Computer Science Internship