Use the following ideas to develop a non-recursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of \(A[1 \dots j]\), extend the answer to find a maximum subarray ending at index \(j + 1\) by using the following observation: a maximum subarray of \(A[1 \dots j + 1]\) is either a maximum subarray of \(A[1 \dots j]\) or a subarray \(A[i \dots j + 1]\), for some \(1 \le i \le j + 1\). Determine a maximum subarray of the form \(A[i \dots j + 1]\) in constant time based on knowing a maximum subarray ending at index \(j\).

The idea is to determine whether \(A[j + 1]\) will be part of the maximum subarray of \(A[1 \dots j + 1]\) or not. If it is a part of the maximum subarray, then we will update our maximum subarray to include \(A[j + 1]\), otherwise we will maintain a temporary sum including \(A[j + 1]\) in case we encounter a sufficiently large element later which can make the future sum greater than the present sum.

In other words, maintain two sum: a maximum subarray ending at current element, and maximum subarray so far.

In line 7, we update our current sum involving current element. And in lines 8-11, we update our best subarray, if required. In lines 12-14, we reset current running sum if it is negative.

A python implementation of this pseudocode is available at the bottom of the page.

#### Runtime Comparison

We can measure the performance of this algorithm along with others as described in Exercise 4.1.3. As expected the linear algorithm runs much much faster than other algorithms (running times are in microseconds):

Size | BruteForce | Recursive | Linear |
---|---|---|---|

20 | 1.1168 | 1.2608 | 0.2176 |

21 | 1.1319 | 1.3312 | 0.2278 |

22 | 1.2343 | 1.3643 | 0.2445 |

23 | 1.3397 | 1.4459 | 0.2512 |

24 | 1.4235 | 1.5344 | 0.2537 |

25 | 1.5350 | 1.6118 | 0.2664 |

26 | 1.6584 | 1.6801 | 0.2766 |

27 | 1.7502 | 1.7495 | 0.2921 |

28 | 1.8662 | 1.8276 | 0.3040 |

29 | 1.9923 | 1.8878 | 0.3043 |

30 | 2.1180 | 1.9716 | 0.3153 |

31 | 2.2915 | 2.0271 | 0.3507 |

The C++ implementation to generate this data can be downloaded from here.

And here is a visual representation of the runtime comparison.

As you can see the brute force run time, \(\Theta(n^2)\), very closely resembles a quadratic curve. Runtime of recursive method is \(\Theta(n \lg n)\) and for linear it is \(\Theta(n)\), the difference between them also can be seen clearly, although both resembles linear curve. That ambiguity will reduce if we can create graph for much higher input size, e.g. \(n = 1000\).