title: Need some hints on this heap-related algorithm design question
body: <p>I meet this problem when practicing algorithm. The problem is like this: There is a street with <strong>n</strong> shops. All the shops have one and only one kind of item, and each shop is associated with a price(a positive integer). The prices of different shops can be the same. People can buy or sell the item at each shop with this price. Now a person traverses through the shops one by one without returning. He can only buy or sold one of this item at each stall. Of course, he can also choose not to do anything at one shop. Now suppose he has infinite money in the beginning, but he still wants to earn as much money as he could. Now given <strong>n</strong> and the prices of each shop, design an algorithm to compute the max amount of money he can earn.</p>
  <p>To be more specific, I will give a sample input and output. Suppose there are 10 shops, and the prices of them are 2，10，8，7，4，4，5，8，9，11. Then if one wants to earn the most money, he needs to buy one item at the 1st, 5th, 6th and 7th shop, and sell one item at the 2nd, 8th, 9th and 10th shop. The money he earns through this process is (10+8+9+11)-(2+4+4+5)=23. Note the item he sells at the 2nd shop must be the one he buys at the 1st shop.</p>
  <p>After trying my best, I think this problem should be solved by heap. I tried to build a min heap by the prices. However, I need more hints on what to do next, or if my idea is correct. Thanks for your help!</p>