# 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:

- 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; }

- 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; }

- 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)

- 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!