[lacker]

If you really think anyone -- short of a faculty-level algorithm specialist at places like CMU -- can be reasonably expected to derive an optimal solution to problems like these on the spot

Eh, you really don't need to be a "faculty-level algorithm specialist" to solve this problem. I wouldn't even really call it dynamic programming.

Just make one pass to calculate the sum of the first n numbers for each n. Call that array prefixSum. Then you make a second pass calculating the lowest prefixSum[i] for i <= n. Call that smallestPrefixSum. The maximum subarray sum is then defined by the largest prefixSum[i] - smallestPrefixSum[i], and you can get the subarray itself with a bit more tracking.

I don't know if it's a great interview question but I think most of the engineers I have hired (at Google or Facebook) would be able to solve this problem on the spot, given 15-20 minutes.

[mercutio2]

Many great engineers get pretty stuck when I ask this question; they try to do dynamic programming and unless they get lucky they get a little lost.

If I ask them to draw a picture, they get your solution pretty much immediately.

So I put this problem in the “gotcha” drawer, because it basically depends on having a eureka moment to get the easy solution.

Still fun to pull it out, but more as extra credit than as a useful interview question.

[TheCoelacanth]

The approach you just described is textbook dynamic programming.

[lacker]

Well, kind of. I would call it dynamic programming if you thought of the algorithm as calling some function many times in an inefficient version, and then caching that result to make it efficient. That is probably how the textbook would describe it, too. I don't think you need to understand dynamic programming to get this, is all.