Maximum sum subarray

The maximum sum sub-array is an array problem in competitive programming where we’re interested in finding the sub-array such that the sum of the elements of the sub-array is as large as possible.

The optimal solution to this problem is Kadane’s algorithm, with a time complexity of $O(n)$ and space complexity of $O(1)$. The core idea is that: if a sub-array that ends at $k$ has a maximum sum, then the sub-array that ends at $k-1$ should also have the maximum sum (up to that point).

int best = 0, sum = 0;
for (auto k: array) {
	sum = max(k, sum + k);
	best = max(best, sum);
}
return best;