Find Maximum Sub-Array Sum using Kadane’s Algorithm

Problem Statement

Given an array of integers, the task is to find the contiguous subarray that has the maximum sum and return that sum.

Key Concepts

1. Dynamic Programming: Kadane’s Algorithm uses dynamic programming principles to maintain the maximum sum at each step.
2. Iteration: The algorithm iteratively examines each element in the array, updating the current maximum subarray sum and the global maximum sum as needed.

Kadane’s Algorithm

• Initialization: Start with two variables: current_max to track the maximum sum of the subarray ending at the current position, and global_max to store the maximum sum found so far.
• Iteration: For each element in the array:
  • Update current_max by comparing the current element alone and the sum of current_max plus the current element.
  • If current_max exceeds global_max, update global_max.
• Result: After iterating through the array, global_max will contain the maximum subarray sum.

C Program for Maximum Subarray Sum (Kadane’s Algorithm)

#include <stdio.h>

// Function to find the maximum subarray sum using Kadane’s Algorithm
int maxSubArraySum(int arr[], int n) {
    int current_max = arr[0]; // Initialize current max
    int global_max = arr[0]; // Initialize global max

    for (int i = 1; i < n; i++) {
        // Update current max
        current_max = (arr[i] > current_max + arr[i]) ? arr[i] : (current_max + arr[i]);

        // Update global max if needed
        if (current_max > global_max) {
            global_max = current_max;
        }
    }

    return global_max;
}

// Main function
int main() {
    int n;

    // Input size of the array
    printf("Enter the number of elements in the array: ");
    scanf("%d", &n);

    int arr[n];

    // Input array elements
    printf("Enter the elements of the array: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Find the maximum subarray sum
    int max_sum = maxSubArraySum(arr, n);
    printf("Maximum Subarray Sum: %d\n", max_sum);

    return 0;
}

Explanation of the Code

1. Function Definition:
   • The maxSubArraySum function takes an array and its size as inputs.
   • It initializes current_max and global_max with the first element of the array.
2. Iterating Through the Array:
   • Starting from the second element, the loop updates current_max to be either the current element alone or the sum of current_max and the current element. This choice decides whether to continue the existing subarray or start a new one.
   • If current_max exceeds global_max, it updates global_max.
3. Main Function:
   • The main function prompts the user to input the size of the array and the array elements.
   • It then calls the maxSubArraySum function and prints the result.

Input and Output Example

Input

cCopy codeEnter the number of elements in the array: 8
Enter the elements of the array: -2 1 -3 4 -1 2 1 -5 4

Output

mathematicaCopy codeMaximum Subarray Sum: 6

Explanation of the Output

In this example, the contiguous subarray [4, -1, 2, 1] has the largest sum, which equals 6. The algorithm efficiently finds this maximum sum in linear time, making it suitable for large arrays.

Conclusion

This C program implements Kadane’s Algorithm to solve the Maximum Subarray Sum problem efficiently. It utilizes dynamic programming principles to ensure a time complexity of O(n). You can test this program with various arrays to observe how it computes the maximum subarray sum, demonstrating the effectiveness of this algorithm in practical applications like financial analysis, performance tracking, and more.