我用来面试屡试不爽的一道题
The Problem
Definition. Given the real vector x[n], compute the maximum sum found in any contiguous subvector.
An Example. If the input vector is
26 then the program returns the sum of x[2..6], or 187.
31
-41
59
26
-53
58
97
-93
-23
84
From Programming Pearls, Copyright 2000, Lucent Technologies Pearls-8-2A Cubic Algorithm
Idea. For all pairs of integers i and j satisfying 0≤i≤ j < n, check whether the sum of x[i.. j] is greater than the maximum sum so far.
Code.
maxsofar = 0 for i = [0, n)
for j = [i, n) sum = 0
for k = [i, j] sum += x[k]
/* sum is sum of x[i..j] */ maxsofar = max(maxsofar, sum)
Run Time. O(n3).
From Programming Pearls, Copyright 2000, Lucent Technologies Pearls-8-3
A Quadratic Algorithm Idea. The sum of x[i..j] is close to the previous
sum, x [ i.. j −1 ]. Code.
maxsofar = 0 for i = [0, n)
sum = 0 for j = [i, n)
sum += x[j] /* sum is sum of x[i..j] */ maxsofar = max(maxsofar, sum)
Run Time. O(n2). Other Quadratic Algorithms?
From Programming Pearls, Copyright 2000, Lucent Technologies Pearls-8-4
Another Quadratic Algorithm
Idea. A ‘‘cumulative array’’ allows sums to be com- puted quickly. If ytd[i] contains year-to-date sales through month i, then sales from March through September are given by ytd[sep] − ytd[ feb].
Implementation. Use the cumulative array cumarr. Initialize cumarr [ i ] = x [ 0 ] + . . . + x [ i ]. The sum of the values in x [ i.. j ] is cumarr [ j ] − cumarr [ i − 1 ].
Code for Algorithm 2b.
cumarr[-1] = 0 for i = [0, n)
cumarr[i] = cumarr[i-1] + x[i] maxsofar = 0
for i = [0, n) for j = [i, n)
sum = cumarr[j] - cumarr[i-1] /* sum is sum of x[i..j] */ maxsofar = max(maxsofar, sum)
Run Time. O(n2). From Programming Pearls, Copyright 2000, Lucent Technologies Pearls-8-5
An O(n log n) Algorithm
The Divide-and-Conquer Schema. To solve a prob- lem of size n, recursively solve two subproblems of size n / 2 and combine their solutions.
The Idea. Divide into two subproblems.
Recursively find maximum in subvectors.
Find maximum crossing subvector.
Return max of ma, mb and mc. Run Time. O(n log n).
a
b
ma
mb
mc
From Programming Pearls, Copyright 2000, Lucent Technologies
Pearls-8-6
Code for the O(N log N) Algorithm
float maxsum3(l, u) if (l > u) /* zero elements */
return 0 if (l == u) /* one element */
return max(0, x[l])
m = (l + u) / 2 /* find max crossing to left */ lmax = sum = 0 for (i = m; i >= l; i--)
sum += x[i]
lmax = max(lmax, sum) /* find max crossing to right */ rmax = sum = 0 for i = (m, u]
sum += x[i] rmax = max(rmax, sum)
return max(lmax+rmax, maxsum3(l, m),
maxsum3(m+1, u))
From Programming Pearls, Copyright 2000, Lucent Technologies
Pearls-8-7
A Linear Algorithm
Idea. How can we extend a solution for x [ 0 .. i − 1 ] into a solution for x [ 0 .. i ]? Key variables:
maxsofar
maxhere
I
Code.
maxsofar = 0 maxhere = 0 for i = [0, n)
/* invariant: maxhere and maxsofar are accurate for x[0..i-1] */ maxhere = max(maxhere + x[i], 0)
maxsofar = max(maxsofar, maxhere)
Run Time. O(n).