LeetCode122. Best Time to Buy an
2017-06-04 本文已影响9人
PentonBin
一、原题
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).
二、题意
给定一个数组，表示某一个特定的股票每一天的价格，则prices[i]则表示第i天该股票的价格。假如在已知每一天的该股票价格的情况下，允许多次买卖，但每一次卖出之后隔天才能买入，问如何找出最大的利润？
三、思路
假设股票的价格如下：[1，3，5，0，9，8，4，7]，则我们可以很快求出其每一天买入，隔天卖出的利润：[2，2，-5，9，-1，-4，3]。
- 第一天：利润为0，因为第一天只能买入，肯定没有利润；
- 第二天：利润为2，因为第二天价格高于第一天价格，卖出会获利；
- 第三天：利润为4，因为第二天不卖的话，留到第三天，则此时利润为4，比第二天卖出的利润还要高；
- 第四天：利润为4，因为前三天都不卖，等到第四天卖出的时候并没有利润，因此需要在第三天卖出，使得在第四天的时候利润最大。此时可以考虑第四天买入；
- 第五天：利润为13，因为如果考虑前四天的情况，在第一天买入第三天卖出，在第四天再买入第五天卖出，则此时利润最大。
......
对比一下每一天的利润情况：[2，2，-5，9，-1，-4，3]，其中的第i个数字表示第(i-1)天买入，第i天卖出的情况
- 第一天：0
- 第二天：第一天买入，第二天卖出的利润是2，2 > 0，所以到第二天最大利润为2；
- 第三天：第二天买入，第三天卖出的利润是2，此时根据上面的推算，我们知道第三天的利润为4，那就是4=2+2，此时能否考虑两天的利润相加？假设这两天利润表示为x，y，则同时选择x和y，也就是x+y就表示第一天买入，第二天卖出，然后第二天买入，第三天再卖出，但我们知道，每一次卖出之后隔天才能买入（题意要求），此时是否冲突？将股票在同一天卖出然后再买入，不就相当于在这一天不买卖一样吗，也就是在这一天持有该股票不进行买卖，所以最后的情况就是，第一天买入，第二天不买卖，第三天卖出。
- 第四天：第三天买入，第四天卖出的利润为-5，-5 < 0，此时应该不考虑，所以到第四天，最大的利润跟第三天一样为4。如果考虑了，那就是2+2+(-5)也就是第一天买入，第二三天不买卖，第四天卖出，最后利润为-1，刚好就是0-1=-1
- 第五天：第四天买入，第五天卖出的利润为9，从上面推算，第五天的最大利润为13，也就是4+9，4为第三天（也是第四天）的最大利润，如果拆成每一天的利润和，则2+2+9的意思就是第一天买入，第三天卖出，第四天买入，第五天卖出，所以此时满足题意的“允许多次买卖，但每一次卖出之后隔天才能买入”
......
梳理一下，对于每一天的利润情况[a，b，c，d，e，f]，
- 如果选择了连续的两个数，假设为b和c，则表示第二天买入，第四天卖出，也就是如果选择了连续两天的利润，则表示中间一天不买卖；
- 如果选择了不是连续的两个数，假设为a和c，则表示第一天买入，第二天卖出，第三天买入，第四天卖出；
综上，选择的数不管是否为连续的数，均满足题意“允许多次买卖，但每一次卖出之后隔天才能买入”的要求，此时只需要将每一天的利润大于0的相加则为所要求的结果。
四、代码
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;
}
};
