[olooney]

Another data point: but I checked my LeetCode history and I actually solved this problem[1] a year ago. It's flagged as "easy" on LeetCode and I have one submission (which was accepted) but I don't even remember solving it, indicating it was probably routine. The problem also has 4809 "thumbs up" vs 177 "thumbs down" which is a strong indicator that others didn't find the problem too hard either; problems that don't match their stated difficultly get downvoted hard.

[1]: https://leetcode.com/problems/maximum-subarray/

[uncletaco]

Did you provide the O(n) solution or O(n3) brute force solution? I think that's the important bit.

[pjscott]

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

[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.

[elihu]

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).

[zucker42]

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.

[olooney]

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