[LeetCode]Best Time to Buy and Sell Stock

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

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

本题难度Easy。

贪婪法

【复杂度】
时间 O(N) 空间 O(1)

【思路】
本题的特点就是卖点一定在买点后，而且要比买点高才行。所以找到最小值​​​min​​​（买点）后，后面只要不比​​min​​​小的一律都属于卖点；如果有比​​min​​​小的值​​p​​​，那么​​p​​设为现在的买点，以此类推。

如果当前值​​p​​​小于最小值​​min​​​，则​​min=p​​​；否则，​​max=Math.max(max,p-min)​​

【代码】

public class Solution {
    public int maxProfit(int[] prices) {
        //require
        if(prices.length<1)
            return 0;
        int max=0,min=prices[0];
        //invariant
        for(int p:prices){
            if(p<min)
                min=p;
            else
                max=Math.max(max,p-min);
        }
        //ensure
        return max;
    }
}