Use the following ideas to develop a nonrecursive, 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 , extend the answer to find a maximum subarray ending at index by using the following observation: a maximum subarray of is either a maximum subarray of or a subarray , for some . Determine a maximum subarray of the form in constant time based on knowing a maximum subarray ending at index .

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

Here is the pseudocode for `FIND-MAXIMUM-SUBARRAY-LINEAR(A, low, high)`

:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

left = 0
right = 0
sum = A[low]
temp_sum = 0
temp_left = 0
for i = low to high
temp_sum = MAX(A[i], temp_sum + A[i])
if temp_sum > sum
sum = temp_sum
right = i
left = temp_left
if temp_sum == A[i]
temp_left = i
return (left, right, sum)

Line 6 determines whether should be part of the maximum subarray of or not. And in lines 7-9, we update our returning sum and right index if the maximum subarray ending at is indeed the maximum subarrya we have seen so far. In lines 10-11, we store the beginning of the maximum subarray when it contains only one element.

We can measure the performance of this algorithm along with others as described in Exercise 4.1.3 to get the following data which shows that as expected linear algorithm runs way faster than other algorithms:

Size | Brute Force | Recursive | Mixed | Linear |
---|---|---|---|---|

5 | 0.070000 | 0.180000 | 0.080000 | 0.040000 |

6 | 0.110000 | 0.230000 | 0.110000 | 0.050000 |

7 | 0.150000 | 0.260000 | 0.160000 | 0.050000 |

8 | 0.220000 | 0.310000 | 0.220000 | 0.060000 |

9 | 0.260000 | 0.370000 | 0.260000 | 0.070000 |

10 | 0.320000 | 0.430000 | 0.330000 | 0.070000 |

11 | 0.370000 | 0.480000 | 0.380000 | 0.080000 |

12 | 0.450000 | 0.550000 | 0.450000 | 0.090000 |

13 | 0.540000 | 0.600000 | 0.550000 | 0.090000 |

14 | 0.570000 | 0.660000 | 0.580000 | 0.100000 |

15 | 0.670000 | 0.710000 | 0.670000 | 0.110000 |

16 | 0.740000 | 0.750000 | 0.740000 | 0.110000 |

17 | 0.820000 | 0.800000 | 0.800000 | 0.120000 |

18 | 0.870000 | 0.860000 | 0.850000 | 0.130000 |

19 | 0.990000 | 0.960000 | 0.970000 | 0.140000 |

20 | 1.060000 | 1.000000 | 0.990000 | 0.150000 |