Friday, March 28, 2014

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i. 
Design an algorithm to find the maximum profit. You may complete at most two transactions. 
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2)
            return 0;
        if (prices.length ==2 )
            return prices[0] < prices[1] ? prices[1] - prices[0] : 0;
            
        int[] maxProf1 = new int[prices.length];
        int maxPrice = prices[prices.length-1];
        maxProf1[maxProf1.length-1] = 0;
        
        for (int i = maxProf1.length-2; i >=0; i--) {
            int profit1;
            if (prices[i] > maxPrice) {
                profit1 = 0;
                maxPrice = prices[i];
            }
            else {
                profit1 = maxPrice - prices[i];
            }
            maxProf1[i] = profit1 > maxProf1[i+1] ? profit1 : maxProf1[i+1];
        }
        
        int minPrice = prices[0];
        int maxProf2 = 0;
        int maxProf = 0;
        for (int j = 0; j < prices.length-2; j++) {
            int profit2;
            if (prices[j] > minPrice) {
                profit2 = prices[j] - minPrice;
            }
            else {
                profit2 = 0;
                minPrice = prices[j];
            }
            maxProf2 = maxProf2 > profit2 ? maxProf2 : profit2;
            int profit = maxProf2 + maxProf1[j];
            maxProf = maxProf > profit ? maxProf : profit;
        }
        
        return maxProf;
    }
}

No comments:

Post a Comment