gs gs122 Dynamic Programming - Kadane’s Algorithm - Quiz No.1

 #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; } 

 #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; }

 #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; }

 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])