Kadane’s Algorithm in C

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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

« Prev - C Program to Implement Knuth-Morris-Pratt Algorithm for Pattern Searching

» Next - C Program to Find a Good Feedback Edge Set in a Graph

Next Steps:

Get Free Certificate of Merit in C Programming
Participate in C Programming Certification Contest
Become a Top Ranker in C Programming
Take C Programming Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Apply for C Internship
Apply for Computer Science Internship
Buy C Books
Practice BCA MCQs
Practice Computer Science MCQs

Recommended Articles: