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.

`#include <stdio.h>`

int main(int argc, char **argv) {

printf("Kadane's Algorithm\n");

int nums[] = { -1, 2, 3, -9, 8, 7, 2 };

int start_index, end_index;

int sum = maximum_consequential_sum(nums, &start_index, &end_index);

printf("maximum sum is %d \n", sum);

printf("maximum index starts at %d \n", start_index);

printf("maximum index ends at %d \n", end_index);

return 0;

`}`

`/*`

`* function performin kadane's Algorithm`

`*/`

int maximum_consequential_sum(int* nums, int*start_index, int*end_index) {

int max_start_index = 0, max_end_index = 0;

int max_sum = 0;

int cur_index, cur_max_sum = 0;

for (cur_index = 0; cur_index < sizeof(nums) / sizeof(nums[0]); cur_index++) {

if (cur_max_sum > max_sum) {

max_sum = cur_max_sum;

max_end_index = cur_index;

`}`

if (cur_max_sum < 0) {

cur_max_sum = 0;

max_start_index = cur_index + 1;

`}`

`}`

start_index = &max_start_index;

end_index = &max_end_index;

return max_sum;

`}`

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.

**Related Posts:**

- Apply for Computer Science Internship
- Apply for C Internship
- Check C Books
- Check Computer Science Books
- Practice BCA MCQs