{"id":840,"date":"2024-10-14T14:17:00","date_gmt":"2024-10-14T08:47:00","guid":{"rendered":"https:\/\/codexplained.in\/?p=840"},"modified":"2025-11-24T15:47:24","modified_gmt":"2025-11-24T10:17:24","slug":"find-maximum-sub-array-sum-using-kadanes-algorithm","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=840","title":{"rendered":"Find Maximum Sub-Array Sum using Kadane\u2019s Algorithm"},"content":{"rendered":"\n

Problem Statement<\/h3>\n\n\n\n

Given an array of integers, the task is to find the contiguous subarray that has the maximum sum and return that sum.<\/p>\n\n\n\n

Key Concepts<\/h3>\n\n\n\n
    \n
  1. Dynamic Programming<\/strong>: Kadane\u2019s Algorithm uses dynamic programming principles to maintain the maximum sum at each step.<\/li>\n\n\n\n
  2. Iteration<\/strong>: The algorithm iteratively examines each element in the array, updating the current maximum subarray sum and the global maximum sum as needed.<\/li>\n<\/ol>\n\n\n\n

    Kadane\u2019s Algorithm<\/h3>\n\n\n\n
      \n
    • Initialization<\/strong>: Start with two variables: current_max<\/code> to track the maximum sum of the subarray ending at the current position, and global_max<\/code> to store the maximum sum found so far.<\/li>\n\n\n\n
    • Iteration<\/strong>: For each element in the array:\n
        \n
      • Update current_max<\/code> by comparing the current element alone and the sum of current_max<\/code> plus the current element.<\/li>\n\n\n\n
      • If current_max<\/code> exceeds global_max<\/code>, update global_max<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • Result<\/strong>: After iterating through the array, global_max<\/code> will contain the maximum subarray sum.<\/li>\n<\/ul>\n\n\n\n

        C Program for Maximum Subarray Sum (Kadane\u2019s Algorithm)<\/h3>\n\n\n
        \n#include <stdio.h>\n\n\/\/ Function to find the maximum subarray sum using Kadane\u2019s Algorithm\nint maxSubArraySum(int arr[], int n) {\n    int current_max = arr[0]; \/\/ Initialize current max\n    int global_max = arr[0]; \/\/ Initialize global max\n\n    for (int i = 1; i < n; i++) {\n        \/\/ Update current max\n        current_max = (arr[i] > current_max + arr[i]) ? arr[i] : (current_max + arr[i]);\n\n        \/\/ Update global max if needed\n        if (current_max > global_max) {\n            global_max = current_max;\n        }\n    }\n\n    return global_max;\n}\n\n\/\/ Main function\nint main() {\n    int n;\n\n    \/\/ Input size of the array\n    printf("Enter the number of elements in the array: ");\n    scanf("%d", &n);\n\n    int arr[n];\n\n    \/\/ Input array elements\n    printf("Enter the elements of the array: ");\n    for (int i = 0; i < n; i++) {\n        scanf("%d", &arr[i]);\n    }\n\n    \/\/ Find the maximum subarray sum\n    int max_sum = maxSubArraySum(arr, n);\n    printf("Maximum Subarray Sum: %d\\n", max_sum);\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
        Explanation of the Code<\/h3>\n\n\n\n
          \n
        1. Function Definition<\/strong>:\n
            \n
          • The maxSubArraySum<\/code> function takes an array and its size as inputs.<\/li>\n\n\n\n
          • It initializes current_max<\/code> and global_max<\/code> with the first element of the array.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • Iterating Through the Array<\/strong>:\n
              \n
            • Starting from the second element, the loop updates current_max<\/code> to be either the current element alone or the sum of current_max<\/code> and the current element. This choice decides whether to continue the existing subarray or start a new one.<\/li>\n\n\n\n
            • If current_max<\/code> exceeds global_max<\/code>, it updates global_max<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • Main Function<\/strong>:\n
                \n
              • The main function prompts the user to input the size of the array and the array elements.<\/li>\n\n\n\n
              • It then calls the maxSubArraySum<\/code> function and prints the result.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                Input and Output Example<\/h3>\n\n\n\n
                Input<\/h4>\n\n\n\n
                cCopy codeEnter the number of elements in the array: 8\nEnter the elements of the array: -2 1 -3 4 -1 2 1 -5 4\n<\/code><\/pre>\n\n\n\n
                Output<\/h4>\n\n\n\n
                mathematicaCopy codeMaximum Subarray Sum: 6\n<\/code><\/pre>\n\n\n\n
                Explanation of the Output<\/h3>\n\n\n\n
                In this example, the contiguous subarray [4, -1, 2, 1]<\/code> has the largest sum, which equals 6<\/code>. The algorithm efficiently finds this maximum sum in linear time, making it suitable for large arrays.<\/p>\n\n\n\n
                Conclusion<\/h3>\n\n\n\n
                This C program implements Kadane\u2019s 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.<\/p>\n