121.Best Time to Buy and Sell Stock

给定价格曲线，进行单次买进卖出，获取最大利润。

思路一：

不断更新买入点（局部最小值），不断更新最大利润（在当前价格卖出，若获取的利润为新高则更新最大利润），直到结束。

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i = 0;
        int max_p = 0;
        int min_p = INT_MAX;
        while (i < prices.size()) {
            if(prices[i] < min_p) {
                min_p = prices[i];
            }
            if(prices[i]-min_p > max_p){
                max_p = prices[i] - min_p;
            }
            i++;
        }
        return max_p;
    }
};

思路二：

用后一天的价格减前一天的价格，得到一个序列，相当于每一天相对于前一天的获利序列，只要求出这个序列的最大子序列即为获得的最大利润。

优化后的代码：

不用将差序列记录下来，直接筛选更新即可。

 public int maxProfit(int[] prices) {
        int maxCur = 0, maxSoFar = 0;
        for(int i = 1; i < prices.length; i++) {
            maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
            maxSoFar = Math.max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }

122.Best Time to Buy and Sell Stock II

不限购买次数，获取最大利润。
所以只要后一天相对前一天可以获利，就可以购买。将差序列中的正数累加即可。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        int max=0;
        for(int i=0;i<len-1;i++) {
            if(prices[i+1] > prices[i]) {
                max += prices[i+1] - prices[i]; 
            }
        }
        return max;
    }
};

123.Best Time to Buy and Sell Stock III

思路

因为规定最多购买两次，所以我把这道题归为找最佳临界点的题。分三种情况，购买0次，1次，2次。我把整个问题分成两部分，每部分分别用Best Time to Buy and Sell Stock I来得出最大利润。第一次在跑最后一个样例时超时了，看了一下样例，发现可以减少对连续重复数字的判断。尽管跑通了代码，时间惨不忍睹。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        if(len < 2) return 0;
        int max_profit=0;
        int profit1=0, max_profit1=0, profit2=0, max_profit2=0;
        for(int i=1; i<len; i++){
            profit1=0, max_profit1=0, profit2=0, max_profit2=0;
            for(int j=0; j<i;){
                profit1 = max(0, prices[j+1]-prices[j]+profit1);
                max_profit1 = max(profit1, max_profit1);
                j++;
                while(j < i-1 && prices[j+1] == prices[j]){
                    j++;
                }
            }
            if(len-i-1 < 2) continue;
            else{
                for(int k=i+1; k<len-1;){
                    profit2 = max(0, prices[k+1]-prices[k]+profit2);
                    max_profit2 = max(profit2, max_profit2);
                    k++;
                    while(k < len-1 && prices[k+1] == prices[k]){
                        k++;
                    }
                }
                
            }
            max_profit = max(max_profit1+max_profit2, max_profit);
            while(i < len-1 && prices[i+1] == prices[i]){
                i++;
            }
        }
        return max(max_profit1+max_profit2, max_profit);
    }
};

正解

在看到我的结果是0.17%的时候是绝望的，又想了一下怎样才能更快，代码的时间复杂度是O(n2)，但我感觉这题可以O(n)过，想到了用一个数组来记录每一个时间点的最大profit，但是后续的好像又需要再算一遍，时间还是O(n2)。事实证明还是我too yong，方向是对了，还是想的太浅。
大神的做法：
第一遍正向记录每个点的最大profit，第二遍从反向记录每个点的最大利润，相加即可。这个思路和 Product of Array Except Self有点像， 两道题都是找一个中间点，计算两边的结果，通过一个数组记录结果，正向一遍，反向更新一遍。

class Solution {
public:
    int maxProfit(vector<int>& p) {
        if (p.size()<2) return 0;
        int v=p[0];
        vector<int> f(p.size(), 0);
        for (int i=1; i<p.size(); ++i) {
            f[i]=max(f[i-1], p[i]-v);
            v=min(v, p[i]);
        }
        int best=f.back(), b=0;
        v=p.back();
        for (int i=p.size()-2; i>=0; --i) {
            b=max(b, v-p[i]);
            v=max(v, p[i]);
            best=max(best, f[i]+b);
        }
        return best;
    }
};