买卖股票的最佳时机I

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

题目

思路

对于某天卖出,显然在前面具有最低价格时买入时,利润最大。因此维护一个最小值,边遍历,边更新。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int _min = INT_MAX;
        int res = 0;
        for(int i = 0; i < prices.size(); i ++){
            _min = min(_min, prices[i]);
            res = max(res,prices[i] - _min);
        }
        return res;
    }
};

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

题目

思路

假设最优解存在这种情况:第i天买入,第j天卖出;

max = p_j - p_i = \sum_{k = i + 1}^j p_k - p_{k - 1}

如上述所示,在不限制买卖次数的情况下,如果第k天价格比第k-1天价格高,那么这可以作为最优解的一部分!

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