買(mǎi)賣(mài)股票的最佳時(shí)機(jī)

給定一個(gè)數(shù)組?prices?，其中?prices[i]?是一支給定股票第 i 天的價(jià)格。

設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易（多次買(mǎi)賣(mài)一支股票）。

注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買(mǎi)前出售掉之前的股票）。

解題思路

本題考察的是貪心算法的應(yīng)用：

• 什么是貪心算法？
  貪心算法（英語(yǔ)：greedy algorithm），又稱(chēng)貪婪算法，是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)（即最有利）的選擇，從而希望導(dǎo)致結(jié)果是最好或最優(yōu)的 。
  
  

• 前一天的價(jià)格減于今天的價(jià)格大于零，然后拿前一天的價(jià)格減于今天的價(jià)格求和。

  
  

  
  

擴(kuò)展解題：

另一種解題方式，也是基于貪心算法，只是判斷的前一天大于今天的價(jià)格，然后拿前一天減于今天的價(jià)格求和。