I don't think this problem is THAT difficult -- I did manage to solve this on my own after a semester of algorithms class and a bit of practice from DP problems. The intuition is that at each index you're either continuing a previous subarray or starting a new one, depending on which one results in a larger sum. It's pretty standard DP stuff, and I'm sure there's many undergrads out there who can bang it out in an interview. Though I personally did it in the comfort of my home and probably wouldn't have come up with it in an interview.