Kadane’s algorithm in C – Dynamic Programming
How do we find a keys that hold maximum consecutive values in sum from the given array?
The usual approach could be O(n^2).
But Kadanes algorithm can perform this same problem in a linear time.
here is the implementation using C
#include <stdio.h>
/*
* @author http://gullele.com
*
*/
void main()
{
printf("Kadane's Algorithmn");
int nums[] = {-1,2,3,-9,8,7,2};
int start_index;
int 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);
}
/*
* Get the maximum subsequent sum from the given array
* function performing 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 <= max_sum ; cur_index++)
{
cur_max_sum += nums[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;
}
The above code is, of course, just for illustration purpose. Make sure to check
for empty array and possible division by zero stuff..
To run this on Linux
1. Save the above file as kadanes.c
2. go to terminal and locate to the file
3. gcc kadanes.c -o kadane
4 run as ./kadane
** you can use this code as you like. As the same time, I am not responsible for anything, in case if you use it.
Thanks
Click here to see more algorithm solutions
Find K Complementary numbers from array Java implementation
Check if there are three numbers a, b, c giving a total T from array A
binary tree problems with solution