?買賣股票的最佳時(shí)機(jī) II
給定一個(gè)數(shù)組，它的第i?個(gè)元素是一支給定股票第?i?天的價(jià)格。
設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易（多次買賣一支股票）捕犬。
注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。
示例 1:
輸入:[7,1,5,3,6,4]輸出:7解釋:在第 2 天（股票價(jià)格 = 1）的時(shí)候買入酵镜，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 碉碉。?? ? 隨后，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入淮韭，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 6-3 = 3 垢粮。
示例 2:
輸入:[1,2,3,4,5]輸出:4解釋:在第 1 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 靠粪。?? ? 注意你不能在第 1 天和第 2 天接連購(gòu)買股票蜡吧，之后再將它們賣出。?? ? 因?yàn)檫@樣屬于同時(shí)參與了多筆交易占键，你必須在再次購(gòu)買前出售掉之前的股票昔善。
示例?3:
輸入:[7,6,4,3,1]輸出:0解釋:在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0。
這道題沒(méi)什么太多說(shuō)的,就是貪心算法? 貼個(gè)貪心算法的定義
貪心算法（又稱貪婪算法）是指畔乙，在對(duì)問(wèn)題求解時(shí)君仆，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)牲距，不從整體最優(yōu)上加以考慮返咱，他所做出的是在某種意義上的局部最優(yōu)解。
貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解牍鞠，關(guān)鍵是貪心策略的選擇咖摹，選擇的貪心策略必須具備無(wú)后效性，即某個(gè)狀態(tài)以前的過(guò)程不會(huì)影響以后的狀態(tài)难述，只與當(dāng)前狀態(tài)有關(guān)萤晴。
剛好在做遞歸的題,寫一點(diǎn)點(diǎn)感想:計(jì)算機(jī)里的很多問(wèn)題都很龐大,但他們又存在一些相關(guān)的地方,比如二叉樹之類的,這個(gè)時(shí)候有可能只需要考慮一步問(wèn)題或者一小塊問(wèn)題,然后讓它自己照著思路去循環(huán)就可以了,我們考慮只需要考慮一下結(jié)果判定 還有一些特殊情況即可.
代碼:
public class Solution
{
? ? public int MaxProfit(int[] prices)
? ? {
? ? ? ? int p = 0;
? ? ? ? int a = 0;
? ? ? ? for (int i = 1; i < prices.Length; i++)
? ? ? ? {
? ? ? ? ? ? p = prices[i] - prices[i - 1];
? ? ? ? ? ? if (p > 0) a += p;
? ? ? ? }
? ? ? ? return a;
? ? }
}
沒(méi)啥好講的 看不懂就多看看...
