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.

?

public class Solution {
    public int maxProfit(int[] prices) {
    	int res = 0;
        if (prices==null || prices.length<=1) {
        	return 0;
        }
        int[] arrA = new int[prices.length];
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
			min = Math.min(min, prices[i]);
			arrA[i] = Math.max(arrA[i-1], prices[i]-min);
		}
        int max = prices[prices.length-1];
        int[] arrB = new int[prices.length];
        for (int i = prices.length-2; i >= 0; i--) {
        	max = Math.max(max, prices[i]);
        	arrB[i] = Math.max(max-prices[i], arrB[i+1]);
		}
        for (int i = 0; i < prices.length; i++) {
			res = Math.max(res, arrA[i]+arrB[i]);
		}
        return res;
    }
}

?

Best Time to Buy and Sell Stock III

原文：http://hcx2013.iteye.com/blog/2241311