# Kadane's Algorithm to find Maximum subarray sum

Kadane’s algorithm is a simple and efficient technique used to solve the maximum subarray problem. This problem involves finding the contiguous subarray within a given array that has the maximum sum among all other contiguous subarrays.

## Maximum Sum of Contiguous Sub Array

Before proceeding to the actual algorithm, let’s first try to understand what contiguous sub arrays are and what maximum subarray sum is.

A contiguous subarray is a continuous sequence of elements within a larger array. Let’s say we have an array with the following values `[2, -3, 4, 1]`. Below are all possible contiguous subarrays along with corresponding sums:

``````[2] -> sum = 2
[2, -3] -> sum = -1
[2, -3, 4] -> sum = 3
[2, -3, 4, 1] -> sum = 4
[-3] -> sum = -3
[-3, 4] -> sum = 1
[-3, 4, 1] -> sum = 2
[4] -> sum = 4
[4, 1] -> sum = 5
``````

Among all these subarrays, the subarray `[4, 1]` has the maximum sum of `5`. So `5` is the maximum subarray sum for the array `[2, -3, 4, 1]`.

There are different techniques to find out the maximum subarray sum for a given array which includes brute force, divide and conquer, dynamic programming etc., but Kadane’s algorithm is efficient and simplest among all other techniques.

## Kadane’s Algorithm & Implementation

Kadane’s algorithm works by keeping track of two values: the maximum subarray sum so far, and the maximum subarray sum ending at the current element. The algorithm starts by initializing these two values to the first element of the array.

Then, as it goes through the array, it either adds the current element to maximum subarray ending at the previous element and increments the current subarray sum. Or it starts a new subarray starting from the current element and resets the current subarray sum. It also keeps track of the maximum sum among all the subarray sums computed so far. Below is the implementation of this algorithm:

``````
def find_max_subarray_sum(arr):
# Initialize the maximum subarray sum so far
max_so_far = arr[0]
# Initialize the maximum subarray sum ending at the current element
max_ending_here = arr[0]

# Iterate through the array starting from the second element
for i in range(1, len(arr)):
# If the current subarray sum is positive, add the current element to it
if max_ending_here > 0:
max_ending_here = max_ending_here + arr[i]
# Otherwise, start a new subarray sum from the current element
else:
max_ending_here = arr[i]

# Update the maximum subarray sum so far
# If the maximum subarray ending at the current element is greater
max_so_far = max(max_so_far, max_ending_here)

# Return the maximum subarray sum so far
print(f"Maximum Subarray Sum for array {arr} is {max_so_far}")
return max_so_far

# Example usage
find_max_subarray_sum([2, -3, 4, 1]) # Expected output: 5
``````

### Time & Space Complexities:

The time complexity of Kadane’s algorithm is `O(n)`, where `n` is the size of the input array. This is because the algorithm iterates through the array once, performing a constant number of operations for each element.

The space complexity of Kadane’s algorithm is O(1), which means it uses a constant amount of additional space, regardless of the size of the input array. The algorithm only requires a few variables to keep track of the current maximum subarray sum and the overall maximum subarray sum, and it does not need to create any additional data structures that grow with the input size.

## Intuition Behind the Algorithm

At each element, Kadane’s algorithm tries to find out the maximum possible sum among all subarray’s ending at the current element. In order to compute it efficiently, we have two options:

1. Add current element to the maximum subarray sum ending at the previous element
2. Start a new subarray starting from the current element and reset the maximum subarray sum ending at current element to it’s value

If the maximum subarray sum ending at the previous element is negative or zero, then going with option 1 will further reduce the subarray sum ending at current element. So we start a new subarray starting from the current element and go with option 2.

If the maximum subarray sum ending at the previous element is positive, it makes sense to use it when considering the maximum subarray ending at current element. So we go with option 1.

By doing this, Kadane’s algorithm is able to efficiently find the maximum subarray in a single pass through the array, without having to try every possible subarray.

TODO: Add animation showing all the steps.