public static int maxProfit(int[] prices){
        if(prices.length == 0){
            return 0;
        }
        //dpLeft[i] is the max profit of one transaction in range [0..i]
        int[] dpLeft = new int[prices.length];
        //dpRight[i] is the max profit of one transaction in range [i..n-1]
        int[] dpRight = new int[prices.length];
        dpLeft[0] = 0;
        dpRight[dpRight.length-1] = 0;
        int min = prices[0];
        int max = prices[prices.length-1];
        int maxProfit = 0;
        //fill the dpLeft array
        for(int i = 1; i < prices.length; i++){
            dpLeft[i] = prices[i] - min > dpLeft[i-1] ? prices[i] - min : dpLeft[i-1];
            min = prices[i] < min ? prices[i] : min;
        }
        //fill the dpLeft array, and calculate profit when each position filled
        for(int i = prices.length-1; i >= 0; i--){
            if(i < prices.length-1){
                dpRight[i] = max - prices[i] > dpRight[i+1] ? max - prices[i] : dpRight[i+1];
            }
            max = prices[i] > max ? prices[i] : max;
            maxProfit = dpLeft[i] + dpRight[i] > maxProfit ? dpLeft[i] + dpRight[i] : maxProfit;
        }
        return maxProfit;
    }