Search This Blog

Thursday, December 27, 2012

LeetCode:Best Time to Buy and Sell Stock III

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) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int min = Integer.MAX_VALUE, max=Integer.MIN_VALUE;
        int [] forward = new int[prices.length], 
               backward = new int[prices.length];
        
        for(int i=0;i<prices.length;i++){
            if(prices[i]>min){
                forward[i]=Math.max(prices[i]-min,forward[i-1]);
            }else{
                if(i>0) forward[i]=forward[i-1];
            }
            min=Math.min(prices[i],min);
            
            if(prices[prices.length-1-i]<max){
                backward[prices.length-1-i]=Math.max(max-prices[prices.length-1-i],backward[prices.length-i]);
            }else{
               if(i>0) backward[prices.length-1-i]=backward[prices.length-i];
            }
            max=Math.max(prices[prices.length-1-i],max);
        }
        
        int res = 0;
        
        for(int i=0;i<prices.length;i++){
            res=Math.max(forward[i]+backward[i],res);
        }
        return res;
    }
}

No comments: