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 $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 returning 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.

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

Line 6 determines whether $A[i]$ should be part of the maximum subarray of $A[1 \dots i]$ or not. And in lines 7-9, we update our returning sum and right index if the maximum subarray ending at $A[i]$ 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