Created
July 25, 2017 18:41
-
-
Save sujaykundu777/a1a72c88291f9ee72aaba02b80159bf7 to your computer and use it in GitHub Desktop.
Kadane's Algorithm Implementation in C
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<stdio.h> | |
//Function to calculate the maximum sum of a sub-array of a given array | |
int maxSumarray(int a[], int size){ | |
int i; | |
int max_sum_so_far=0; | |
int max_ending_here = 0; | |
for(i=0;i<size;i++){ | |
max_ending_here = max_ending_here + a[i]; | |
if(max_ending_here < 0){ | |
max_ending_here =0; | |
} | |
if(max_sum_so_far < max_ending_here){ | |
max_sum_so_far = max_ending_here; | |
} | |
} | |
return max_sum_so_far; | |
} | |
int main(){ | |
int i,size; | |
printf("Enter the size of the array "); | |
scanf("%d",&size); | |
int a[size]; | |
printf("\n Enter the elements of the array"); | |
for(i=0; i<size; i++){ | |
scanf("%d",&a[i]); | |
} | |
int max_sum = maxSumarray(a,size); | |
printf("\n The Maximum Sum of the Sub Array is : %d",max_sum); | |
return 0; | |
} |
The idea of the Kadane’s algorithm is to look for all positive contiguous segments of the array.
Kadane’s algorithm works if the input array contains at least one non-negative element.
In your example, the array consists of all negative integers, and hence, doesn't provide the expected output.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The code doesn't give correct output in case of negative numbers as in case of array :[-1,-2,-3,-4]