Kadane’s Algorithm, algorithm and time complexity, with example in C,C++,Python and java

The Maximum Subarray Sum problem is a classic programming challenge where we need to find the contiguous subarray with the largest sum within a given array. Kadane’s Algorithm provides an elegant solution to this problem. In this blog post, we will explore the algorithm, its time complexity, and provide code examples in four popular programming languages: C, C++, Python, and Java.

Algorithm:
Kadane’s Algorithm is based on the concept of dynamic programming and works by iterating through the array and maintaining two variables: currentMax and globalMax. The currentMax variable keeps track of the maximum subarray sum ending at the current index, while globalMax stores the maximum subarray sum encountered so far.

The algorithm begins by initializing both variables to the value of the first element in the array. Then, for each subsequent element, it compares the element itself with the sum of the current element and the currentMax. If the current element is greater, the currentMax is updated to start a new subarray. Otherwise, the currentMax is updated with the sum of the current element and the previous currentMax. At each step, the globalMax is updated if the currentMax exceeds its value.

At the end of the iteration, the globalMax will contain the maximum subarray sum.

Time Complexity:
Kadane’s Algorithm has a time complexity of O(n), where n is the size of the input array. The algorithm requires only a single pass through the array, making it highly efficient.

Code Examples:

1. C:

#include <stdio.h>

int maxSubarraySum(int arr[], int n) {
    int currentMax = arr[0];
    int globalMax = arr[0];

    for (int i = 1; i < n; i++) {
        currentMax = (arr[i] > currentMax + arr[i]) ? arr[i] : currentMax + arr[i];
        globalMax = (currentMax > globalMax) ? currentMax : globalMax;
    }

    return globalMax;
}

int main() {
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(arr) / sizeof(arr[0]);

    int maxSum = maxSubarraySum(arr, n);

    printf("The maximum subarray sum is: %dn", maxSum);

    return 0;
}

1. C++:

#include <iostream>
#include <algorithm>

using namespace std;

int maxSubarraySum(int arr[], int n) {
    int currentMax = arr[0];
    int globalMax = arr[0];

    for (int i = 1; i < n; i++) {
        currentMax = max(arr[i], currentMax + arr[i]);
        globalMax = max(currentMax, globalMax);
    }

    return globalMax;
}

int main() {
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(arr) / sizeof(arr[0]);

    int maxSum = maxSubarraySum(arr, n);

    cout << "The maximum subarray sum is: " << maxSum << endl;

    return 0;
}

1. Python:

def max_subarray_sum(arr):
    current_max = arr[0]
    global_max = arr[0]

    for i in range(1, len(arr)):
        current_max = max(arr[i], current_max + arr[i])
        global_max = max(current_max, global_max)

    return global_max

arr = [-2, -3, 4, -1, -2, 1, 5, -3]
max_sum = max_subarray_sum(arr)
print("The maximum subarray sum is:", max_sum)

1. Java:

class Main {
    static int maxSubarraySum(int[] arr) {
        int currentMax = arr[0];
        int globalMax = arr[0];

        for (int i = 1; i < arr.length; i++) {
            currentMax = Math.max(arr[i], currentMax + arr[i]);
            globalMax = Math.max(currentMax, globalMax);
        }

        return globalMax;
    }

    public static void main(String[] args) {
        int[] arr = {-2, -3, 4, -1, -2, 1, 5, -3};

        int maxSum = maxSubarraySum(arr);

        System.out.println("The maximum subarray sum is: " + maxSum);
    }
}

Conclusion:
Kadane’s Algorithm provides an efficient solution for finding the maximum subarray sum within a given array. By maintaining two variables, currentMax and globalMax, the algorithm achieves a time complexity of O(n) by performing a single pass through the array. In this blog post, we explained the algorithm and provided code examples in C, C++, Python, and Java. Next time you encounter a problem requiring finding the maximum subarray sum, you can confidently utilize Kadane’s Algorithm. Happy coding!