Kadane’s Algorithm

• Time : O(n)
• Space : O(1)

int kadanesAlgorithm(vector<int> array) {
	int res = array[0];
	for(int i = 0, sum = 0; i < array.size(); i++) {
		sum = max(sum + array[i], array[i]);
		res = max(sum, res);
	}
  return res;
}