---
# System prepended metadata

title: '-Maximum subarray sum (Kadane''s Algo)'
tags: [Medium]

---

# -Maximum subarray sum (Kadane's Algo)
###### tags: `Medium`

![](https://i.imgur.com/9N4rTND.png)

紀錄當前最大的subarray sum（two possible outcome）：
1. 為前一個的最大subarray sum + 自己
2. 自己

另外同時紀錄最大的subarray sum

```cpp=
int kadanesAlgorithm(vector<int> array) {
  // Write your code here.
	int maxHere = array[0];
	int maxSoFar = array[0];
	for (int i = 1; i < array.size(); i++){
		maxHere = max((maxHere + array[i]), array[i]);
		maxSoFar = max(maxSoFar, maxHere);
	}
  return maxSoFar;
}
```
