# 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

#### Test Cases

Input | Output |
---|---|

[-2,1,-3,4,-1,2,1,-5,4] | 6 |

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

Array Index | Explanation | Variable Values |
---|---|---|

0 | So starting with the first element of the array, since it’s the first element at index 0, we don’t need to perform the calculation so the localMax and globalMax are both the element at index 0, which is -2. | globalMax = -2 localMax = -2 |

1 | Then for index 1, arr[1] is the element 1, we perform the first calculation of finding the max value of arr[i] and (arr[i] + localMax).The maximum value of 1 and (1 + -2 = -1) is 1.So we set the localMax to 1 and since 1 is greater than the current globalMax, which is currently set to -2, we update the global max to 1 as well. | globalMax = 1 localMax = 1 |

2 | Then we move onto the index 2 which is the value -3. So the max of -3 and (-3 + 1 = -2) is -2.This means that previous elements in the array are still valuable to finding the max, so we update the localMax to -2. We don’t change the globalMax. | globalMax = 1 localMax = -2 |

3 | Index 3 is the value 4. The max of 4 and (4 + -2 = 2) is 4. So we change the localMax to 4. Effectively we are saying that the previous elements are now irrelevant and we are restarting the subarray from index 3. 4 is greater than the current globalMax so we update it to the new value. | globalMax = 4 localMax = 4 |

4 | Index 4 is the value -1. The max of -1 and (-1 + 4 = 3) is 3. Update localMax to 3. globalMax stays at 4. | globalMax = 4 localMax = 3 |

5 | Index 5 is the value 2. The max of 2 and (2 + 3 = 5) is 5. Update localMax to 5. Update globalMax to 5. | globalMax = 5 localMax = 5 |

6 | Index 6 is the value 1. The max of 1 and (1 + 5 = 6) is 6. Update the localMax to 6. Update the globalMax to 6. | globalMax = 6 localMax = 6 |

7 | Index 7 is the value -5. The max of -5 and (-5 + 6 = 1) is 1. Update localMax to 1. globalMax stays at 6. | globalMax = 6 localMax = 1 |

8 | Index 8 is the value 4. The max of 4 and (4 + 1) is 5. Update localMax to 5. globalMax stays at 6. | globalMax = 6 localMax = 5 |

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)

See Also

If you liked this explanation, you might also like this interview question that was asked by Google.