LeetCode: 121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

    int maxProfit(vector<int>& prices) {
        if(prices.size()<=1) return 0;

        int min=prices[0];
        int res=0;
        for(int i=1;i<prices.size();++i){
            if(min>prices[i])min=prices[i];
            if(prices[i]-min > res)res=prices[i]-min;
        }
        return res;
    }

从前往后遍历 如果遇到比min小的 对min修改
因为如果后面大的只能对前面小的进行比较 相对于修改前的min,已经没有意义了

http://xzh.i3geek.com

发表评论

发表回复

*

沙发空缺中,还不快抢~