Nit: The brute-force solution for the one-dimensional case is O(n^2), not O(n^3).

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

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.

The brute force solution that seems most obvious to me is to pick a starting index and an ending index out of all possible indexes such that start < end, and calculate the sum of that sub-array (keeping the biggest result).

This is O(N^3) because iterating over index pairs is O(N^2) and doing the sum is O(N).

Brute is choosing every index pair (n^2) and calculating the sun of their subarray (n). With prefix sums you can get to n^2.

O(n). Faster than 75% of accepted solutions. :)