Data Structure Questions and Answers – Kadane’s Algorithm

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

Answer: c
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

Answer: b
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

Answer: d
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.
advertisement
advertisement

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

Answer: b
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:

Note: Join free Sanfoundry classes at Telegram or Youtube
#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

Answer: d
Explanation: The maximum of sum and ans, is stored in ans. So, the answer is max_num(sum, ans).
advertisement

6. What is the time complexity of Kadane’s algorithm?
a) O(1)
b) O(n)
c) O(n2)
d) O(5)
View Answer

Answer: b
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

Answer: a
Explanation: Kadane’s algorithm uses a constant space. So, the space complexity is O(1).
advertisement

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

Answer: d
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

Answer: d
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

Answer: c
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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.