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
If you have any question or suggestion or you have found any error in this solution, please leave a comment below.