Best Time to Buy and Sell Stock是一个系列，包括easy到hard各种难度的题目，我把它们都放在一起来总结起来。

[EASY] 121. Best Time to Buy and Sell Stock

这道题是这个系列的开篇之作。题目内容是给你一个数组，里面的数组表示当天的股价，需要你在便宜的适合购买股票，然后在后面的时间里找到一个高点卖出，一共只能进行一次买入和一次卖出，计算出哪一天的利润最高。

这道题没用到dp，直接保存当前最小值，然后当前值和当前最小值的差值最大者就是结果

Solution

时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        int minP = prices[0];
        int money = 0;
        for (int i = 1; i < prices.size(); i++) {
            money = max(prices[i] - minP, money);
            minP = min(minP, prices[i]);
        }
        return money;
    }
};

[EASY] 122. Best Time to Buy and Sell Stock II

这道题与第一题不一样的地方在于可以进行多次交易，需要求出交易得到的最大利润。解题思路就是维持当前的最小值，一旦当前的prices[i]大于最小值，说明就可以做一次交易，然后再把最小值设为当前的prices[i]。

其实就是找到每一个上升的数字序列。时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        int minp = prices[0];
        int profile = 0;
        for (int i = 0; i < prices.size(); i++) {
            if (prices[i] > minp)  profile += prices[i] - minp;
            minp = prices[i];
        }
        return profile;
    }
};

[MEDIUM] 714. Best Time to Buy and Sell Stock with Transaction Fee

这道题的区别在于需要