Kadane’s Algorithm (Dynamic Programming)

# Kadane’s Algorithm (Dynamic Programming)

Kadane’s algorithm is a dynamic programming strategy for solving the Maximum Subarray problem.

E.g. Given an array[−2, 1, −3, 4, −1, 2, 1, −5, 4], the maximum subarray is [4, −1, 2, 1], with sum 6.

Elegant recursion formula:

$$sum = Max \left\{ \begin{array}{lr} a[i]\\ maximumSubArray[i – 1] + a[i]\\ \end{array} \right.$$

code: