# Kadane's Algorithm

#### 2022-06-09

---

##### Data structures:

#array

##### Algorithms:

#algorithm #Kadane_s_algorithm

##### Difficulty:

#CS_analysis #difficulty-easy

##### Time complexity:

O(n)

##### Related problems:

##### Resources:

- [Explainer article](https://medium.com/@rsinghal757/kadanes-algorithm-dynamic-programming-how-and-why-does-it-work-3fd8849ed73d)

---

### What is Kadane's Algorithm?

It's a kind of dynamic programming. You calculate A[n] by calculating A[n - 1], which makes it O(n)

==local_maximum at index i is the maximum of (A[i] and the sum of A[i] and local_maximum at index i-1).==

> Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem: the maximum subarray ending at the previous position) this algorithm can be viewed as a simple example of dynamic programming. Kadane’s algorithm is able to find the maximum sum of a contiguous subarray in an array with a runtime of **_O(n)_**.

### When to use it?

According my analyze [[Leetcode Best-Time-To-Buy-And-Sell-Stock#Thoughts| here]], we should use it when these conditions are met:

- You want to find the value of the highest peak or lowest valley
- The direction you search is mono-directional
- The current value can be obtained from or, is related to the value before this one.
