[gjm11]

Just as a data point: I read the paper and thought "that sounds like it might be fun, so let's have a go" and wrote down a (correct aside from an off-by-one error) O(n) solution in a couple of minutes. I am not a faculty-level algorithm specialist at CMU. I don't recall seeing a solution to this particular problem before. I am a mathematician working in industry doing kinda-algorithm-y things, though. There are at least two other people working at my (small) employer whom I would expect to be able to find an O(n) solution fairly quickly. (To quantify: >=75% chance that they find one, given 20 minutes to think.)

The fact that the first couple of people to consider the problem didn't find efficient solutions doesn't mean that finding efficient solutions is a super-hard problem. Grenander wasn't really interested in the 1-dimensional problem but in the (I think distinctly harder) 2-dimensional problem, and I don't think he was really an algorithms guy. (That's not a polite way of saying he wasn't very smart; he clearly was, but I don't think finding optimal algorithms for things was what he was most interested in.)

For the avoidance of doubt, I don't think you're likely to get much insight into interview candidates by seeing whether they spot the most efficient solution to a problem like this unaided -- even an extremely strong candidate might just happen not to think of a good approach, especially under stressful interview conditions. (It might still be a useful question if a less adversarial approach is taken -- discuss the problem with the candidate, get a sense of how they think, and nudge them in a helpful direction if they get stuck -- or if the only question is whether the candidate can find and implement any approach, which for this problem I think any reasonably competent software developer should be able to do since you can basically just translate the question into straightforward but inefficient code that does the job.)

I'm not sure whether we actually disagree or not, but I do think you may be overstating the difficulty of this particular problem.

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

[tropicalia]

You're right and I stand corrected - it's not that hard of a problem. I found this out when (sometime later) I actually sat down to solve it, without considering any of the hints posted elsewhere in this thread.

At least there seems to be some general agreement (within the thread) that, while not super-hard -- it's still basically a "eureka problem" -- that is, even among what we may consider to be adequately good engineers -- some will get the visual solution more or less right away; but a fair percent (25 or more) won't.

And that's given ideal circumstances -- working alone and in unhurried circumstances. Throw in the (considerable) distraction of having to think aloud in front of other people (who themselves may not exactly be providing the most relaxing vibe, to say the lease), and all the other stress that comes with interviewing -- and I'll bet that 25 percent failure rate rises quite considerably, in turn.

And in many cases -- if you fail just one of these "eureka" problems -- and maybe fail to provide the expected canned response to a "behavioral" question or two -- than that's pretty much all it takes. To be considered, you know, "not a fit".

As to why I jumped the gun -- fatigue, probably, from being fed a few too many "cute" problems like these.

[chapium]

Maximum subarray is a typical problem solved by a dynamic programming algorithm.

[lacker]

It's possible to use dynamic programming but it's such a simple example you don't really have to. If you're familiar with dynamic programming at all, you should be able to get it - it would be pretty reasonable to assign this as a introductory homework program for the dynamic programming section of an algorithms class.