Kadane’s Algorithm

This is a maximum-subarray-sum problem

Purpose

To find a non-empty subarray with the largest sum in O(n) time, note that for an array of all negatives, we will just return a sub-array of size 1 of the largest number in that array.

Note that a sub-array must be contiguous.

Fundamentally, there is a subproblem of finding the maximum-sum subarray that ends at a position k.

• The subarray only contains the element at position k
• The subarray consists of a subarray that ends at position k-1, followed by the element at position k.
• In the latter case, the goal is to find the a subarray with the maximum sum. Since the subarray with ending posiiton k-1 will have the current maximum sum, we can solve this problem efficiently by calculating the maximum subarray sum for each ending position from left to right.
• At each step we ask the question, does adding element k to our sum make it better or worse, if it makes it worse, let’s start a new subarray and start a new sum.

int best = 0, sum = 0; 
for (int k = 0; k < n; k++) { 
	sum = max(array[k], sum+array[k]); 
	best = max(best,sum); 
} 
cout << best << "\n";
 

This algorithm can be modified to solve Leetcode - Best Time to Buy and Sell Stock with applications in 2-pointer and sliding window situations.