[LintCode] 149 Best Time to Buy and Sell Stock 解题报告

Description
Say you have an array for which the i^th 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
Given array [3,2,3,1,2], return 1.



思路
遍历数组，并且维护一个最小股价和一个最大利润。
如果当前股价 - 最小股价 > 最大利润，那么我们更新最大利润。
最小股价为当前股价和之前最小股价的较小值。



Code

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        if (prices == null || prices.length == 0) {
            return 0;
        }
        
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = Integer.MIN_VALUE;
        
        for (int i = 0; i < prices.length; i++) {
            int currPrice = prices[i];
            int currProfit = currPrice - minPrice;
            minPrice = Math.min(minPrice, currPrice);
            maxProfit = Math.max(maxProfit, currPrice - minPrice);
        }
        
        return maxProfit;
    }
}