*Programming Pearls by John Bentley*

The challenge is; given an array of numeric values such as

**31, -41, 59, 26, -53, 58, 97, -93, -23, 84**

write a program to find the maximum sum of a sub-array of

*contiguous*values in the array. For example, the maximum sum in the above is the values

**59 + 26 + -53 + 58 + 97 = 187**

The following is a brute force method written in VB that just computes every possible sum from every possible sub-array. It has performance proportional to N[sup]2[/sup] where N is the number of elements in the array.

CHALLENGE: Can you develop a faster algorithm than this?

(The author gives several in the book and I'll post them later.)

Code:

```
Private Sub Command26_Click()
Dim X() As Long
Dim cbuf As String
Dim N As Long
Dim UB As Long
ReDim X(999) [COLOR=black cyan]' Set the size of the array here[/color]
[COLOR=black cyan]' This just generates some numbers for you[/color]
UB = UBound(X)
cbuf = ""
For N = 0 To UB
X(N) = Rnd * 100
If Rnd(X(N)) <= 0.45 Then X(N) = -2 * X(N)
cbuf = cbuf & X(N) & ", "
If (N > 0 And N Mod 10 = 0) Or N = UB Then
Debug.Print Left(cbuf, Len(cbuf) - 2)
cbuf = ""
End If
Next
BruteForce X
MsgBox "Done"
End Sub
Private Sub BruteForce(X() As Long)
Dim MaxSoFar As Long
Dim Sum As Long
Dim StartAt As Long, EndAt As Long
Dim L As Long, I As Long, U As Long, N As Long
Dim tm As Double
[COLOR=black cyan]' This is the brute force approach.[/color]
tm = Timer
N = UBound(X)
MaxSoFar = 0
For L = 0 To N
For U = L To N
Sum = 0
For I = L To U
Sum = Sum + X(I)
If Sum > MaxSoFar Then
MaxSoFar = Sum
StartAt = L
EndAt = U
End If
Next
Next
Next
Debug.Print
Debug.Print "BRUTE FORCE METHOD"
Debug.Print UBound(X) + 1 & " Elements"
Debug.Print MaxSoFar, StartAt, X(StartAt), EndAt, X(EndAt)
Debug.Print (Timer - tm) & " seconds"
End Sub
```

Just as an aside ... Bentley in his book says

*"... on the computer I usually use (1986), the above takes 1 hour for a 1,000 element array ..."*

On mine (2006) it takes 13 seconds.

[small]No! No! You're not thinking ... you're only being logical.

- Neils Bohr[/small]