I'd like to have your opinion on the difficulty of the following interview question:

Find the subarray with maximum sum in an array of integers in O(n) time.

This trivial sounding problem was made famous by Jon Bentley in his Programming Pearls where he uses it to demonstrate algorithm design techniques.

On a scale of 1-10, 1 being the FizzBuzz (or HoppityHop) test and 10 being implement the C stdlib function malloc(), how would you rank the above problem?

I think the people who can best answer this question are those who have read Programming Pearls and have tried to solve this problem on their own. To motivate those who haven't, 'Programming Pearls' gets featured many times in the 'Top 10 programming books' list.