一梧奢、原題
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
二、題意
給定一個(gè)數(shù)組撞叨，表示某一個(gè)特定的股票每一天的價(jià)格妇拯，則prices[i]則表示第i天該股票的價(jià)格饿肺。假如在已知每一天的該股票價(jià)格的情況下诗箍，允許多次買賣碗降，但每一次賣出之后隔天才能買入匿又，問如何找出最大的利潤方灾？
三、思路
假設(shè)股票的價(jià)格如下：[1碌更，3裕偿，5，0痛单，9嘿棘，8，4桦他，7]蔫巩，則我們可以很快求出其每一天買入，隔天賣出的利潤：[2快压，2圆仔，-5，9蔫劣，-1坪郭，-4，3]脉幢。
- 第一天：利潤為0歪沃，因?yàn)榈谝惶熘荒苜I入，肯定沒有利潤嫌松；
- 第二天：利潤為2沪曙，因?yàn)榈诙靸r(jià)格高于第一天價(jià)格，賣出會(huì)獲利萎羔；
- 第三天：利潤為4液走，因?yàn)榈诙觳毁u的話，留到第三天贾陷，則此時(shí)利潤為4缘眶，比第二天賣出的利潤還要高；
- 第四天：利潤為4髓废，因?yàn)榍叭於疾毁u巷懈，等到第四天賣出的時(shí)候并沒有利潤，因此需要在第三天賣出慌洪，使得在第四天的時(shí)候利潤最大顶燕。此時(shí)可以考慮第四天買入凑保；
- 第五天：利潤為13，因?yàn)槿绻紤]前四天的情況割岛，在第一天買入第三天賣出愉适，在第四天再買入第五天賣出犯助，則此時(shí)利潤最大癣漆。
......
對(duì)比一下每一天的利潤情況：[2，2剂买，-5惠爽，9，-1瞬哼，-4婚肆，3]，其中的第i個(gè)數(shù)字表示第(i-1)天買入坐慰，第i天賣出的情況
- 第一天：0
- 第二天：第一天買入较性，第二天賣出的利潤是2，2 > 0结胀，所以到第二天最大利潤為2赞咙；
- 第三天：第二天買入，第三天賣出的利潤是2糟港，此時(shí)根據(jù)上面的推算攀操，我們知道第三天的利潤為4，那就是4=2+2秸抚，此時(shí)能否考慮兩天的利潤相加速和？假設(shè)這兩天利潤表示為x，y剥汤，則同時(shí)選擇x和y颠放，也就是x+y就表示第一天買入，第二天賣出吭敢，然后第二天買入碰凶，第三天再賣出，但我們知道省有，每一次賣出之后隔天才能買入（題意要求）痒留，此時(shí)是否沖突？將股票在同一天賣出然后再買入蠢沿，不就相當(dāng)于在這一天不買賣一樣嗎伸头，也就是在這一天持有該股票不進(jìn)行買賣，所以最后的情況就是舷蟀，第一天買入恤磷，第二天不買賣面哼，第三天賣出。
- 第四天：第三天買入扫步，第四天賣出的利潤為-5魔策，-5 < 0，此時(shí)應(yīng)該不考慮河胎，所以到第四天闯袒，最大的利潤跟第三天一樣為4。如果考慮了游岳，那就是2+2+(-5)也就是第一天買入政敢，第二三天不買賣，第四天賣出胚迫，最后利潤為-1喷户，剛好就是0-1=-1
- 第五天：第四天買入，第五天賣出的利潤為9访锻，從上面推算褪尝，第五天的最大利潤為13，也就是4+9期犬，4為第三天（也是第四天）的最大利潤河哑，如果拆成每一天的利潤和，則2+2+9的意思就是第一天買入哭懈，第三天賣出灾馒，第四天買入，第五天賣出遣总，所以此時(shí)滿足題意的“允許多次買賣睬罗，但每一次賣出之后隔天才能買入”
......
梳理一下，對(duì)于每一天的利潤情況[a旭斥，b容达，c，d垂券，e花盐，f]，
- 如果選擇了連續(xù)的兩個(gè)數(shù)菇爪，假設(shè)為b和c算芯，則表示第二天買入，第四天賣出凳宙，也就是如果選擇了連續(xù)兩天的利潤熙揍，則表示中間一天不買賣；
- 如果選擇了不是連續(xù)的兩個(gè)數(shù)氏涩，假設(shè)為a和c届囚，則表示第一天買入有梆，第二天賣出，第三天買入意系，第四天賣出泥耀；
綜上，選擇的數(shù)不管是否為連續(xù)的數(shù)蛔添，均滿足題意“允許多次買賣痰催，但每一次賣出之后隔天才能買入”的要求，此時(shí)只需要將每一天的利潤大于0的相加則為所要求的結(jié)果作郭。
四陨囊、代碼
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty()){
return 0;
}
int sum = 0;
for(int i = 1; i < prices.size(); ++i){
if(prices[i] - prices[i-1] > 0){
sum += (prices[i] - prices[i-1]);
}
}
return sum;
}
};
