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:

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

code: