[olooney]

According to the Wikipedia page[1], the brute force solution is O(n^3) for the one-dimensional case. They don't give an algorithm, but the obvious pseudo-code is:

    highest_total = 0
    for all i from 0 to length-1:
        for all j from i+1 to length-1:
            total = 0
            for all k from i to j-1:
               total += data[k]
            highest_total = max(total, highest_total)
    return highest_total

It takes three nested loops, with the third being the sum from i to j. This is obviously a very naive algorithm, but that's why it's called brute force. According to Wikipedia, Grenander apparently improved this to O(n^2), and then Jay Kadane came up with the first O(n) solution. For the 2D case, brute force is actually O(n^6).

[1]: https://en.wikipedia.org/wiki/Maximum_subarray_problem

[pjscott]

Huh! That's a bit more brutishly forceful than I was expecting, and I concede the point. It hadn't occurred to me to stick that innermost loop in there rather than keeping a running sum in the second loop.