Page 31 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes
Or, to put it another way, if we use A[j : k]to denote the subarray of A from index j to index
k, then the maximum subarray problem is to find the subarray A[j : k] that maximizes the
sum of its values. In addition to being considered a good problem for testing the thinking
skills of prospective employees, the maximum subarray problem also has applications in
pattern analysis in digitized images. An example of this problem is shown in Figure 1.

Figure 1: An Instance of the Maximum Subarray Problem
In this case, the maximum subarray is A[3 : 6], that is, the maximum sum is s
3,6
A First Solution to the Maximum Subarray Problem
Our first algorithm for the maximum subarray problem, which we call MaxsubSlow, is
shown in Algorithm given below. It computes the maximum of every possible subarray
summation, s , of A separately.
j,k
Algorithm MaxsubSlow(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.
for j ← 1 to n do

m ← 0 // the maximum found so far
for k ← j to n do
s ← 0 // the next partial sum we are computing
for i ← j to k do

s ← s + A[i]
if s > m then
m ← s
return max

It isn’t hard to see that the MaxsubSlow algorithm is correct. This algorithm calculates the
partial sum, s , of every possible subarray, by adding up the values in the subarray from
j,k
a to a . Moreover, for every such subarray sum, it compares that sum to a running maximum
j k
and if the new value is greater than the old, it updates that maximum to the new value. In
the end, this will be maximum subarray sum.
Contd...

24 LOVELY PROFESSIONAL UNIVERSITY