题目描述

假设你有一个数组，其中第i个元素表示第i天某个股票的价格。

如果您只允许完成至多一笔交易（即买入一只股票并卖出一只股票），则设计一种算法以找到最大利润。

必须先购买股票再出售股票。

样例

Example 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第二天买(price = 1) ，在第五天卖 (price = 6), 利润 = 6-1 = 5.

Example 2:

输入: [7,6,4,3,1]
输出: 0
解释: 这个例子中没有完成交易。

算法1 贪心算法

Time $O(n)$, Space $O(1)$

最容易想到的做法是每两天都分别计算得到一个数字再比较，这样的复杂度是$O(n^2)$，弃之。

贪心法的含义是选当前最优。遍历一次，更新当前最低价格和最高利润。

C++ 代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<2) return 0;
        int profit = 0, low = prices[0]; //当前最低价格的初始值不是0
        for(int i = 1; i < prices.size(); ++i){
            profit = max(profit, prices[i]-low);
            low = min(low, prices[i]);
        }
        return profit;
    }
};