4.1 The maximum-subarray problem

4.1-1

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

It will return the greatest element of \(A\).

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

BRUTE-FORCE-FIND-MAXIMUM-SUBARRAY(A)
    n = A.length
    max-sum = -∞
    for l = 1 to n
        sum = 0
        for h = l to n
            sum = sum + A[h]
            if sum > max-sum
                max-sum = sum
                low = l
                high = h
    return (low, high, max-sum)

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 original algorithm returns a negative sum, returning 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]\), is either a maximum subarray of \(A[1..j]\) or a 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
16

ITERATIVE-FIND-MAXIMUM-SUBARRAY(A)
    n = A.length
    max-sum = -∞
    sum = -∞
    for j = 1 to n
        currentHigh = j
        if sum > 0
            sum = sum + A[j]
        else
            currentLow = j
            sum = A[j]
        if sum > max-sum
            max-sum = sum
            low = currentLow
            high = currentHigh
    return (low, high, max-sum)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用