Maximum Subarray Sum

A problem that has a straightforward $O\left(n^3\right)$ solution. However, by designing a better algorithm, this can be solved in as fast as $O\left(n\right)$ time.

Problem Statement

Given an array of n numbers, the task is to calculate the maximum subarray sum (the largest possible sum of a sequence of consecutive values in an array).

This problem becomes more interesting when there may be negative values in the array.

Algorithms

1. Go through all possible subarrays, calculate the sum of values in each subarray and maintain the maximum sum (outer loop for the entire array, inner loop for subarrays, another inner loop to calculate incremental sums)

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

2. Notice that the inner loop which basically just re-computes sums (since our first pointer always goes back to a) is not needed. Instead we can calculate the sum whenever we move the subarray to save us a loop which effectively reuses the sum of the previous subarray.

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

3. The most efficient solution uses Kadane’s Algorithm