I was reading CLRS "divide and conquer" section and this problem was the example, but the example was introduced as a "best time to buy and sell stock" problem. So I just realized that actually in this problem every element in the list can be considered as the difference between two stock prices in two consecutive days. The O(n) solution is the same idea as the solution to the stock price problem, and it is easier to understand for some people, I guess.