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


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

另外同時紀錄最大的subarray sum

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;
}