leetcode - Best Time to Buy and Sell Stock

leetcode - 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.

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

 只能买入卖出一次，找最大差值

遍历整个vector，不断更新minPrice，并求当前元素与minPrice的差值，如果大于maxPrice，则更新maxPrice

最小值越小，后面的大的差值可能越大，但是同时由于必须是后面的值减前面的值，所以每次都求后面的值与最小值的差，如果是更大的差值才更新maxPrice

leetcode - Best Time to Buy and Sell Stock

原文：http://www.cnblogs.com/shnj/p/4741466.html