Skip to content

# 4.1 The maximum-subarray problem

## 4.1-1

What does $\text{FIND-MAXIMUM-SUBARRAY}$ return when all elements of $A$ are negative?

If the index of the greatest element of $A$ is $i$, it returns $(i, i, A[i])$.

## 4.1-2

Write pseudocode for the brute-force method of solving the maximum-subarray problem. Your procedure should run in $\Theta(n^2)$ time.

  1 2 3 4 5 6 7 8 9 10 11 12 MAX-SUBARRAY-BRUTE-FORCE(A) n = A.length max-so-far = -∞ for l = 1 to n sum = 0 for h = l to n sum = sum + A[h] if sum > max-so-far max-so-far = sum low = l high = h return (low, high) 

## 4.1-3

Implement both the brute-force and recursive algorithms for the maximum-subarray problem on your own computer. What problem size $n_0$ gives the crossover point at which the recursive algorithm beats the brute-force algorithm? Then, change the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than $n_0$. Does that change the crossover point?

On my computer, $n_0$ is $37$.

If the algorithm is modified to used divide and conquer when $n \ge 37$ and the brute-force approach when $n$ is less, the performance at the crossover point almost doubles. The performance at $n_0 - 1$ stays the same, though (or even gets worse, because of the added overhead).

What I find interesting is that if we set $n_0 = 20$ and used the mixed approach to sort $40$ elements, it is still faster than both.

## 4.1-4

Suppose we change the definition of the maximum-subarray problem to allow the result to be an empty subarray, where the sum of the values of an empty subarray is $0$. How would you change any of the algorithms that do not allow empty subarrays to permit an empty subarray to be the result?

If the algorithm returns a negative sum, toss out the answer and use an empty subarray instead.

## 4.1-5

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 $A[1..j]$, extend the answer to find a maximum subarray ending at index $j + 1$ by using the following observation: a maximum subarray $A[i..j + 1]$, for some $1 \le i \le j + 1$. Determine a maximum subarray of the form $A[i..j + 1]$ in constant time based on knowing a maximum subarray ending at index $j$.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 MAX-SUBARRAY-LINEAR(A) n = A.length max-sum = -∞ ending-here-sum = -∞ for j = 1 to n ending-here-high = j if ending-here-sum > 0 ending-here-sum = ending-here-sum + A[j] else ending-here-low = j ending-here-sum = A[j] if ending-here-sum > max-sum max-sum = ending-here-sum low = ending-here-low high = ending-here-high return (low, high, max-sum) 

The variables are intended as follows:

• $low$ and $high$ demarcate a maximum subarray found so far.
• $max\text-sum$ gives the sum of the values in a maximum subarray found so far.
• $ending\text-here\text-low$ and $ending\text-here\text-high$ demarcate a maximum subarray ending at index $j$ . Since the high end of any subarray ending at index $j$ must be $j$, every iteration of the for loop automatically sets $ending\text-here\text-high = j$.
• $ending\text-here\text-sum$ gives the sum of the values in a maximum subarray ending at index $j$.

The first test within the for loop determines whether a maximum subarray ending at index $j$ contains just $A[j]$. As we enter an iteration of the loop, $ending\text-here\text-sum$ has the sum of the values in a maximum subarray ending at $j - 1$. If $ending\text-here\text-sum + A[j] > A[j]$, then we extend the maximum subarray ending at index $j - 1$ to include index $j$. (The test in the if statement just subtracts out $A[j]$ from both sides.) Otherwise, we start a new subarray at index $j$, so both its low and high ends have the value $j$ and its sum is $A[j]$. Once we know the maximum subarray ending at index $j$, we test to see whether it has a greater sum than the maximum subarray found so far, ending at any position less than or equal to $j$. If it does, then we update $low$, $high$, and $max\text-sum$ appropriately.

Since each iteration of the for loop takes constant time, and the loop makes $n$ iterations, the running time of $\text{MAX-SUBARRAY-LINEAR}$ is $O(n)$.