Kadane’s Algorithm in C

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

Algorithm for Kadane’s Algorithm

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.

Frequently Asked Questions (FAQs)

Q1. Is Kadane’s algorithm hard?
Ans. Difficulty: Medium: Kadane’s Algorithm: Given an array of integers, find the subarray with the highest/lowest possible sum.

Q2. Kadane’s algorithm is either DP or greedy.
Ans. Kadane’s Algorithm can be regarded as both greedy and DP. As we can see, we keep a running sum of integers, and when it falls below zero, we reset it to zero.

Q3. Where is Kadane’s algorithm used?
Ans. The famous problem of Maximum Subarray Sum is solved using Kadane’s Algorithm. This Algorithm solves the problem in linear time.

Q4. Who made the Kadane algorithm?
Ans. Jay Kadane of Carnegie-Mellon University came up with the idea.