LeetCode题目:Best Time to Buy and Sell Stock

By | 2012 年 12 月 3 日

这个很简单,一次扫描完成。只需要找到最大增长即可。
从前往后,用当前价格减去此前最低价格,就是在当前点卖出股票能获得的最高利润。
扫描的过程中更新最大利润和最低价格就行了。
O(n)



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 (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.



代码:52ms过大集合

class Solution {
public:
    int maxProfit(vector &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (prices.size() <= 1)
            return 0;
        int low = prices[0];
        int maxp = 0;
        for(int i = 1; i < prices.size(); ++i) {
            int profit = prices[i] - low;
            if(maxp < profit) maxp = profit;
            if(low > prices[i]) low = prices[i];
        }
        return maxp;
    }
};

2 thoughts on “LeetCode题目:Best Time to Buy and Sell Stock

  1. Pingback: LeetCode题目:Best Time to Buy and Sell Stock - uniEagle | Tianlong Yun

发表评论

电子邮件地址不会被公开。 必填项已用*标注