Kadane’s Algorithm in C

Kadane’s Algorithm is used to find the subarray with the largest sum in a given array of integers. This algorithm operates in O(n) time complexity, making it very efficient for this problem.

Algorithm Explanation

The idea behind Kadane’s Algorithm is to iterate through the array while keeping track of the maximum sum of the subarray that ends at the current position. This is achieved using two variables:

• currentMax: The maximum sum of the subarray that ends at the current position.
• globalMax: The maximum sum of any subarray found so far.

For each element in the array, we update currentMax as the maximum of the current element and the sum of the current element and the previous currentMax. Then, we update globalMax as the maximum of globalMax and currentMax.

C Code Implementation

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

// Function to find the subarray with the largest sum
int findMaxSubarraySum(int nums[], int size) {
    // Initialize currentMax and globalMax with the first element of the array
    int currentMax = nums[0];
    int globalMax = nums[0];

    // Iterate through the array starting from the second element
    for (int i = 1; i < size; i++) {
        // Update currentMax to the maximum of the current element and the sum of current element and currentMax
        if (nums[i] > currentMax + nums[i]) {
            currentMax = nums[i];
        } else {
            currentMax = currentMax + nums[i];
        }

        // Update globalMax if currentMax is greater than globalMax
        if (currentMax > globalMax) {
            globalMax = currentMax;
        }
    }

    // Return the globalMax which is the largest sum of subarray found
    return globalMax;
}

// Main function to test the algorithm
int main() {
    // Example array
    int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int size = sizeof(nums) / sizeof(nums[0]);

    // Find and print the maximum subarray sum
    int maxSubarraySum = findMaxSubarraySum(nums, size);
    printf("The maximum subarray sum is: %d\n", maxSubarraySum);

    return 0;
}

Explanation of the C Code

In the C code above:

• The function findMaxSubarraySum takes an array of integers and its size as input and returns the sum of the subarray with the largest sum.
• We initialize currentMax and globalMax with the first element of the array.
• We iterate through the array starting from the second element. For each element, we update currentMax and then globalMax if necessary.
• The main function provides an example array, calls the findMaxSubarraySum function to find, and prints the maximum subarray sum.

Output

For the example array {-2, 1, -3, 4, -1, 2, 1, -5, 4}, the output will be:

The maximum subarray sum is: 6

The subarray with the largest sum is {4, -1, 2, 1} which sums to 6.