Friday, August 15, 2014

[LeetCode] 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).

解题思路:
1. 扫描数组从左到右,算出leftmaxprofit
2. 扫描数组从右到左,算出rightmaxprofit
3. 同时从左到右扫描 leftmaxprofit and rightmaxprofit, 算出最大收益,leftmaxprofit + rightmaxprofit

Java code:

 public int maxProfit(int[] prices) {
       int maxProfit = 0;
        int[] leftMaxProfit = new int[prices.length];
        int[] rightMaxProfit = new int[prices.length];
        
        int minPrice = Integer.MAX_VALUE;
        
        for(int i = 0; i < prices.length; i++){   
            minPrice = minPrice < prices[i]? minPrice : prices[i];
            int profit = prices[i] - minPrice;
            leftMaxProfit[i] = maxProfit > profit ? maxProfit : profit;
        }
        
        int maxPrice = 0;
        maxProfit = 0;
        
        for(int i = prices.length; i > 0; i--){
            int profit = maxPrice - prices[i-1];
            maxProfit = maxProfit > profit ? maxProfit : profit;
            rightMaxProfit[i-1] = maxProfit;
            maxPrice = maxPrice > prices[i-1]? maxPrice : prices[i-1];
        }
        
        maxProfit = 0;
        
        for(int i = 0; i < prices.length; i++){
           int profit = leftMaxProfit[i] + rightMaxProfit[i];
           maxProfit = profit > maxProfit? profit : maxProfit;
        }
        
        return maxProfit;
    }

No comments:

Post a Comment