  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on May 11, 2023 by Prepbytes Kadane’s algorithm is both greedy and DP. As can be seen, we keep a running sum of integers and reset it to zero when it falls below zero. This is due to the fact that continuing with a negative sum is far worse than beginning again. The C programming language program for Kadane’s algorithm will be covered on this page.

## What exactly is Kadane’s Algorithm?

Kadane’s Algorithm is a dynamic programming algorithm that iterates. It computes the maximum sum subarray ending at a specific position by using the maximum sum subarray from the previous position.

### How do I apply Kadane’s Algorithm?

You are given an integer array A and must find and print the subarray with the highest sum. It should be noted that the largest sum

Let us now look at Kadane’s algorithm in C.

1. Take the array size from the user and store it in a variable called n.
2. Declare an array of length n.
3. Take n array elements from the user.
4. Create a variable called max_sum that holds the required maximum sum of subarray and curr_sum, and set max_sum to INT_MIN and curr_sum to 0.
5. Iterate through the array, and for each ith value, add it to curr_sum and compare it to max_sum as follows:
• If (max_sum curr_sum) then max_sum = curr_sum.
• Now, if curr_sum is 0, set curr_sum to 0.
6. After a complete iteration, we will get the result that is stored in the max_sum variable. ### Implementation of Kadane’s Algorithm in C

```#include <stdio.h>
#include <limits.h>

int main()
{
int n;
scanf("%d", &n);
int arr[n];
for(int i=0; i<n; i++)
scanf("%d", &arr[i]);

int max_sum = INT_MIN, curr_sum =0;
for(int i=0; i<n; i++){
curr_sum += arr[i];
if(max_sum < curr_sum)
max_sum = curr_sum;
if(curr_sum < 0)
curr_sum = 0;
}

printf("%d ", max_sum);
return 0;
}
```

Output :

User input:

``````5
1 2 3 4 5 ``````

Output :

``15 ``

Conclusion
The article covers Kadane’s method, which is a dynamic programming algorithm that computes the maximum sum subarray ending at a certain place by utilizing the preceding position’s maximum sum subarray. The algorithm is greedy, as is DP. The article includes a C algorithm for implementing Kadane’s algorithm, which involves taking an integer array and determining the subarray with the largest sum. Iterating through the array, keeping track of the maximum sum and the current sum, and resetting the current sum to zero when it goes below zero, is how the implementation is done. The article includes C code for implementing Kadane’s algorithm.