[leetcode] BestTimetoBuyandSellStock

package leetcode;

/**
* <pre>
* 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.
* </pre>
*/
public class BestTimetoBuyandSellStock {
    //slow.
    public class Solution {
        public int maxProfit(int[] prices) {
            if (prices == null || prices.length == 0)
                return 0;
            int result = prices[prices.length - 1] - prices[0];
            for (int step = prices.length - 2; step > 0; step--) {
                for (int i = 0; i + step < prices.length; i++) {
                    result = Math.max(result, prices[i + step] - prices[i]);
                }
            }
            return result;
        }
    }

    public class Solution2 {
        public int maxProfit(int[] prices) {
            if (prices == null || prices.length == 0)
                return 0;
            int result = 0;
            int min = prices[0];
            for (int i = 1; i < prices.length; i++) {
                result = Math.max(result, prices[i] - min);
                min = Math.min(min, prices[i]);
            }
            return result;
        }
    }
}