In this tutorial, we will see how to solve the maximum sub array sum problem efficiently using the Kadane’s Algorithm.

## Maximum subarray sum

What is the maximum subarray sum problem? Say, you’re given an array of integers, of size n, and you’re asked to find the contiguous sub array with maximum sum, how will you do that? More specifically, if you’re asked to find the sum of such contiguous subarray, how will you approach the problem?

## Naive approach

The brute force solution involves finding all possible contiguous sub arrays and finding the sum, to find the maximum possible sum. For this, we need to run two loops, one iterating over the array elements to fix the leftmost element of the subarray, and the other loop keeps iterating on the right of this chosen element to fix the rightmost element of the subarray.

What is the time complexity of this approach? Since we’re running two for loops, it’ll take `O(n²)` time complexity.

Can this be improved? Can this be solved in a single pass?

• Iterate over the array and keep track of two variables `max_so_far` and `max_ending_here`.
• Initially, both `max_so_far` and `max_ending_here` are initialized to zero.
• At index `i`, `max_ending_here` computes the subarray with largest sum ending at `i`, and, `max_so_far` computes the subarray with the largest sum anywhere in `A[0..i]`.
• Keep updating the two variables at every iteration, and at the end of the pass, `max_so_far` holds the maximum subarray sum.
• The pseudo code for implementing the above approach :
```     Initialize :
max_so_far = 0
max_ending_here = 0
Loop over the elements of the array :
At index i, of the array
max_ending_here = max_ending_here+arr[i]
if(max_ending_here < 0)
max_ending_here = 0
if(max_ending_here > max_so_far)
max_so_far = max_ending_here
return max_so_far

```

## Implementation in Python

``````def maxSubArraySum(a,size):
(max_so_far, max_ending_here)=(0,0)
for num in a:
max_ending_here = max_ending_here+num
if(max_ending_here > max_so_far):
max_so_far = max_ending_here
if(max_ending_here < 0):
max_ending_here=0
return max_so_far

if __name__ == "__main__":
arr = [-2,1,-3,4,-1,2,1,-5,4]
res = maxSubArraySum(arr,9)
print("Output : ",res)``````
``````Output:  6
``````

## Implementation in JAVA

``````import java.util.*;
import java.io.*;

{
public static void main(String[] args)
{
int arr[] = {-2,1,-3,4,-1,2,1,-5,4};
int n = arr.length;
int max_so_far=0, max_ending_here=0;
for(int i=0; i<n; i++)
{
max_ending_here = max_ending_here+arr[i];
if(max_ending_here > max_so_far)
max_so_far = max_ending_here;
if(max_ending_here < 0)
max_ending_here = 0;
}

System.out.println(max_so_far);

}
}``````

## Complexity analysis

Since this approach works in a single pass, the time complexity is `O(n)`. It doesn’t utilize any extra memory, and hence, the space complexity is constant, i.e., `O(1)`.

This algorithm uses “optimal substructures” i.e., the maximum subarray ending at each position is computed from the maximum subarray ending at the previous position, and hence, this approach is a simple application of dynamic programming.