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
This is O(N^3) because iterating over index pairs is O(N^2) and doing the sum is O(N).
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.
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.