-Maximum subarray sum (Kadane's Algo)

tags: `Medium`

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

紀錄當前最大的subarray sum（two possible outcome）：

為前一個的最大subarray sum + 自己
自己

另外同時紀錄最大的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;
}