Select optimal subintervals from array
Search for maximum subsequence sum problem, here you will find a linear time solution. Bentley's "Programming Pearls" gives several alternative algorithms and some history. The linear time solution is obvious in hindsight, but it took several tries by experts to come up with it...