Algorithms Lecture 13: Maximum Sub-array Problem using Divide-and-Conquer

California State University, Sacramento
Spring 2018

Algorithms
by Ghassan Shobaki

Text book: Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, 3rd Edition, MIT Press, Cambridge (2009)

Note: There is a dynamic programming algorithm (Kadane's algorithm) that solves this problem in linear time, but it is not discussed here. This lecture is limited to the divide-and-conquer algorithm.

Correction:
Line 3 in the pseudo-code (written at Minute 13) should be
L = MaxSubarray(A, p, q)
The third parameter should be q not q-1

MaxCrossingSubarray(A, p, q, r)
leftSum = -∞
sum = 0
for i = q down to p
sum = sum + A[i]
if sum Greater than leftSum
leftSum = sum
rightSum = -∞
sum = 0
for j = q+1 to r
sum = sum + A[j]
if sum Greater than rightSum
rightSum = sum
return leftSum + rightSum