# Max Subarray Problem – Kadane’s Algorithm (Dynamic Programming)

Contents

#### Problem

The max subarray problem is a problem where you have to find the contiguous subarray (containing at least one number) which has the largest sum, and return the sum.

The problem can be found here

#### Solution

The way to solve this problem is use Kadane’s algorithm:

The way that this algorithm works is through dynamic programming.

We traverse the array and for each element perform the calculation to find the maximum value of either arr[i] and (arr[i] + localMax).

This works because for a given index if the value of the element at the index is greater than the sum of that element and the localMax, it is such that previous subarray elements do not contribute any increase in value to current max. So we don’t need the elements from the previous indexes to get a max subarray.

If the element at the current index is not greater than the sum of that element and the localMax then it means that in order to find the max subarray, we need the previous elements plus the current element.

So the answer for the given input is the value of the globalMax at the end which is 6.

And with this solution we scored the fastest ever time on Leet Code:

#### Runtime Complexity

Algorithm performs on linear time complexity O(n) as the array is only traversed once.

#### Space Complexity

Algorithm performs in constant space O(1)