@@ -0,0 +1,2292 @@
+package com.freetymekiyan.algorithms.level.easy;%0A%0A/**%0A * Say you have an array for which the ith element is the price of a given%0A * stock on day i.%0A * %3Cp%3E%0A * If you were only permitted to complete at most one transaction (ie, buy one%0A * and sell one share of the stock), design an algorithm to find the maximum%0A * profit.%0A * %3Cp%3E%0A * Tags: Array, DP%0A */%0Aclass BestTimeStock %7B%0A%0A    public static void main(String%5B%5D args) %7B%0A        int%5B%5D prices = %7B1, 4, 2%7D;%0A        System.out.println(maxProfit(prices));%0A    %7D%0A%0A    /**%0A     * Optimized bottom-up approach%0A     * O(n) Time, O(1) Space%0A     * Just record yesterday's profit%0A     * Update min, max and profit%0A     * If next price is bigger, it's only possible to update the profit%0A     * If next price is smaller or equal, it's only possible to update min%0A     */%0A    public static int maxProfit(int%5B%5D prices) %7B%0A        if (prices == null %7C%7C prices.length %3C 2) %7B%0A            return 0; // need at least 2%0A        %7D%0A        int max = 0;%0A        int min = prices%5B0%5D; // track the minimum of profit array before cur ele%0A        for (int i = 1; i %3C prices.length; i++) %7B // note that i starts from 1%0A            min = Math.min(min, prices%5Bi%5D); // update min%0A            if (prices%5Bi%5D %3E prices%5Bi - 1%5D) %7B%0A                max = Math.max(max, prices%5Bi%5D - min);%0A            %7D%0A        %7D%0A        return max;%0A    %7D%0A%0A    /**%0A     * DP, bottom-up.%0A     * Keep track of minimum price of the stock.%0A     * Keep track of the maximum profit before today.%0A     * Get the maximum profit of today, and compare with previous maximum.%0A     * Update maximum if today's profit is larger.%0A     * Stop until the array is fully traversed.%0A     * O(n) Time, O(n) Space.%0A     */%0A    public static int maxProfitB(int%5B%5D prices) %7B%0A        if (prices == null %7C%7C prices.length %3C 2) %7B%0A            return 0; // need at least 2 days%0A        %7D%0A        int min = prices%5B0%5D;%0A        int max = 0;%0A        int len = prices.length;%0A        int%5B%5D history = new int%5Blen%5D;%0A        for (int i = 0; i %3C len - 1; i++) %7B%0A            min = min %3C prices%5Bi%5D ? min : prices%5Bi%5D;%0A            if (i %3E 0) %7B // skip first day%0A                history%5Bi%5D = Math.max(history%5Bi - 1%5D, prices%5Bi%5D - min);%0A                max = history%5Bi%5D %3E max ? history%5Bi%5D : max;%0A            %7D%0A        %7D%0A        return max;%0A    %7D%0A%7D%0A

move best time stock to easy