 Kadane's algorithm

ID: kadane-s-algorithm

For input

a_{1}, \dots, a_{n}

, let

E_{i}

be the largest sum of a nonempty contiguous block ending at

i

E_{1} = a_{1}

and

E_{i} = max (a_{i}, E_{i - 1} + a_{i})

is exact: an optimal block either starts at

i

or extends an optimal block ending at

i - 1

. The answer is

max_{i} E_{i}

. Keeping only the current

E_{i}

and best value gives linear time complexity and constant extra space complexity.

 New to topics? Read the docs here!