一、原題
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à)格，賣出會獲利；
- 第三天：利潤為4，因?yàn)榈诙觳毁u的話，留到第三天，則此時(shí)利潤為4，比第二天賣出的利潤還要高；
- 第四天：利潤為4，因?yàn)榍叭於疾毁u，等到第四天賣出的時(shí)候并沒有利潤，因此需要在第三天賣出，使得在第四天的時(shí)候利潤最大。此時(shí)可以考慮第四天買入；
- 第五天：利潤為13，因?yàn)槿绻紤]前四天的情況，在第一天買入第三天賣出，在第四天再買入第五天賣出，則此時(shí)利潤最大。
......
對比一下每一天的利潤情況：[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í)滿足題意的“允許多次買賣，但每一次賣出之后隔天才能買入”
......
梳理一下，對于每一天的利潤情況[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;
}
};
