暴力法比较直接,贪心法比较美丽。
为啥可以用贪心呢?因为买必须在卖之前,因此每到一步都可以获取到这一步为止的最佳状态,不断这个最佳状态即可。
class Solution { public: /** * * @param prices int整型vector * @return int整型 */ int maxProfit(vector &prices) { // write code here int minVal = prices[0], profit = 0; for (int i = 1; i < prices.size(); ++i) { if (prices[i] < minVal) minVal = prices[i]; profit = max(profit, prices[i] - minVal); } return profit; } };