250+ TOP MCQs on Kadane’s Algorithm and Answers

Data Structure Multiple Choice Questions 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

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

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

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

Answer: b
Clarification: 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
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)
Answer: d
Clarification: 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(n²)
d) O(5)

Answer: b
Clarification: 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(n²)
d) None of the mentioned

Answer: a
Clarification: 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
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

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

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

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