C Program to Implement Kadane’s Algorithm

This is a C Program to Implement Kadane Algorithm. Kadane algorithm is to used to obtain the maximum subarray sum from an array of integers.

Here is source code of the C Program to Implement Kadane’s Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <stdio.h>
  2.  
  3. int main(int argc, char **argv) {
  4.     printf("Kadane's Algorithm\n");
  5.     int nums[] = { -1, 2, 3, -9, 8, 7, 2 };
  6.     int start_index, end_index;
  7.     int sum = maximum_consequential_sum(nums, &start_index, &end_index);
  8.     printf("maximum sum is %d \n", sum);
  9.     printf("maximum index starts at %d \n", start_index);
  10.     printf("maximum index ends at %d \n", end_index);
  11.     return 0;
  12. }
  13.  
  14. /*
  15.  * function performin kadane's Algorithm
  16.  */
  17. int maximum_consequential_sum(int* nums, int*start_index, int*end_index) {
  18.     int max_start_index = 0, max_end_index = 0;
  19.     int max_sum = 0;
  20.     int cur_index, cur_max_sum = 0;
  21.     for (cur_index = 0; cur_index < sizeof(nums) / sizeof(nums[0]); cur_index++) {
  22.         if (cur_max_sum > max_sum) {
  23.             max_sum = cur_max_sum;
  24.             max_end_index = cur_index;
  25.         }
  26.         if (cur_max_sum < 0) {
  27.             cur_max_sum = 0;
  28.             max_start_index = cur_index + 1;
  29.         }
  30.     }
  31.     start_index = &max_start_index;
  32.     end_index = &max_end_index;
  33.     return max_sum;
  34. }

Output:

$ gcc KadaneAlgorithm.c
$ ./a.out
 
Kadane's Algorithm
maximum sum is 0 
maximum index starts at 4199878 
maximum index ends at 2293400

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

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.