Page 33 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes
if S “ S”1 > m then
k j
m ← S “ S”1
k j
return max
Analyzing the MaxsubFaster Algorithm
The correctness of the MaxsubFaster algorithm follows along the same arguments as for
the MaxsubSlow algorithm, but it is much faster. In particular, the outer loop, for index j,
will iterate n times, its inner loop, for index k, will iterate at most n times, and the steps
inside that loop will only take O(1) time in each iteration. Thus, the total running time of
the MaxsubFaster algorithm is O(n ), which improves the running time of the MaxsubSlow
2
algorithm by a linear factor. True story: a former student of one of the authors gave this
very algorithm during a job interview for a major software company, when asked about
the maximum subarray problem, correctly observing that this algorithm beats the running
3
time of the naive O(n )-time algorithm by a linear factor. Sadly, this student did not get a
job offer, however, and one possible reason could have been because there is an even
better solution to the maximum subarray problem, which the student didn’t give.

A Linear-Time Maximum Subarray Algorithm
We can improve the running time for solving the maximum subarray further by applying
the intuition behind the prefix summations idea to the computation of the maximum
itself. That is, what if, instead of computing a partial sum, S , for t = 1,2, . . . , n, of the values
t
of the subarray from a to a , we compute a “partial maximum,” M , which is the maximum
1 t t
summation of a subarray of A[1 : t] that ends at index t?
Such a definition is an interesting idea, but it is not quite right, because it doesn’t include
the boundary case where we wouldn’t want any subarray that ends at t, in the event that all
such subarrays sum up to a negative number. So, recalling our notation of letting s
j,k
denote the partial sum of the values in A[j : k].
{ }
M t = max 0,max{S , j t }
≤ jt
Note that if we know all the M values, for t = 1,2, . . . , n, then the solution to the maximum
t
subarray problem would simply be the maximum of all these values. So let us consider
how we could compute these M values.
t
The crucial observation is that, for t ≥ 2, if we have a maximum subarray that ends at t, and
it has a positive sum, then it is either A[t : t] or it is made up of the maximum subarray that
ends at t – 1 plus A[t]. If this were not the case, then we could make an even bigger subarray
by swapping out the one we chose to end at t – 1 with the maximum one that ends at t – 1,
which would contradict the fact that we have the maximum subarray that ends at t. In
addition, if taking the value of maximum subarray that ends at t – 1 and adding A[t] makes
this sum no longer be positive, then M = 0, for there is no subarray that ends at t with a
t
positive summation. In other words, we can define M = 0 as a boundary condition, and use
0
the following formula to compute M , for t = 1,2, . . . , n:
t
t
M t = t −1 + max{0,M A [ ]}
Therefore, we can solve the maximum subarray problem using the algorithm,
MaxsubFastest, shown in Algorithm given below.
Algorithm MaxsubFastest(A):

Input: An n-element array A of numbers, indexed from 1 to n.

Contd...

26 LOVELY PROFESSIONAL UNIVERSITY