Page 32 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 2: Data Structure Operations and Algorithms Complexity

Notes
Incidentally, both the calculating of subarray summations and the computing of the
maximum so far are examples of the accumulator design pattern, where we incrementally
accumulate values into a single variable to compute a sum or maximum (or minimum).
This is a pattern that is used in a lot of algorithms, but in this case it is not being used in the
most efficient way possible.
Analyzing the running time of the MaxsubSlow algorithm is easy. 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 innermost loop, for index i, will iterate at most n times. Thus, the running time of
3
the MaxsubSlow algorithm is O(n ). Unfortunately, in spite of its use of the accumulator
design pattern, giving the MaxsubSlow algorithm as a solution to the maximum subarray
problem would be a bad idea during a job interview. This is a slow algorithm for the
maximum subarray problem.

An Improved Maximum Subarray Algorithm
We can design an improved algorithm for the maximum subarray problem by observing
that we are wasting a lot of time by recomputing all the subarray summations from
scratch in the inner loop of the MaxsubSlow algorithm. There is a much more efficient way
to calculate these summations. The crucial insight is to consider all the prefix sums, which
are the sums of the first t integers in A for t = 1,2, . . . , n. That is, consider each sum, S , which
t
is defined as
t
.
..
s t = a 1 + a 2 + + a t = ∑ a i
i =1
If we are given all such prefix sums, then we can compute any subarray summation, s , in
j,k
constant time using the formula:
=s − S S
, j k k j −1
where we use the notational convention that S = 0. To see this, note that
0
k j −1
S k − S j −1 = ∑ a i − ∑ a i
i =1 i =1
k
= ∑ a i = s j ,, k
= ij
0
where we use the notational convention that ∑ i a = 0 .
=1 i
We can incorporate the above observations into an improved algorithm for the maximum
subarray problem, called MaxsubFaster, which we show in Algorithm given below.

Algorithm MaxsubFaster(A):
Input: An n-element array A of numbers, indexed from 1 to n.
Output: The subarray summation value such that A[j] + · · · + A[k] is maximized.

S ← 0 // the initial prefix sum
0
for i ← 1 to n do
S ← S ”1 + A[i]
i i
for j ← 1 to n do
m ← 0 // the maximum found so far

for k ← j to n do
Contd...

LOVELY PROFESSIONAL UNIVERSITY 25