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.

 

public class Solution {
    // keep track of min price & max profit
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;
        int minprice = prices[0];
        int maxprofit = 0;
        for (int i = 1; i < prices.length; i++) {
            int currprofit = prices[i] - minprice;
            if (currprofit > maxprofit)
                maxprofit = currprofit;
            if (prices[i] < minprice)
                minprice = prices[i];
        }
        return maxprofit;
    }
}

 

评论

1 楼 qb_2008 2015-04-14  

这其实是一道贪婪。最开始的想法是穷举所有(买入日，卖出日）的组合，O(n^2)。
然后发现对固定的卖出日而言，找最好的买入日是一个贪婪问题，即找在卖出日之前
的最小价格日。最后发现在从前到后遍历时，可以顺便算出相对当前卖出日的最佳
买入日，于是O(n)。