5.9

O(n) Kadane-style algorithm

Core idea: while scanning once through the array keep
 • cur_sum – the largest sum of a subrange that ends at the current index k, together with its start index cur_start;
 • best_sum – the largest sum seen so far and its corresponding indices best_start, best_end.

At each element A[k] (1-based):
1. Decide whether to extend the previous range or start a new one:
   if cur_sum + A[k] ≥ A[k] then extend (cur_sum += A[k]);
   else set cur_sum = A[k] and cur_start = k.
2. If cur_sum > best_sum update best_sum, best_start = cur_start, best_end = k.

def largest_subrange(A): # A indexed from 1 to n best_start = best_end = 1 cur_start = 1 best_sum = cur_sum = A[1] for k in range(2, len(A)+1): if cur_sum + A[k] >= A[k]: cur_sum += A[k] # extend else: cur_sum = A[k] # start new range cur_start = k if cur_sum > best_sum: # better than any seen? best_sum = cur_sum best_start = cur_start best_end = k return best_start, best_end, best_sum

The loop touches each element once and uses only O(1) extra space, hence the running time is [math]O(n)[/math]. The returned pair [math](best\_start,\;best\_end)[/math] maximizes [math]S=\sum_{k=best\_start}^{best\_end} A[k][/math].

Back to Chapter 5