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 twotransactions.
Example
Given an example [4,4,6,1,1,4,2,5], return 6.
与前几题不同，这道题需要同时考虑左侧区间和右侧区间共同的最大值。可以创建两个数组， 一个包做index左侧最大的获利值，一个数组保存index右侧最大的获利值。最后计算两个数组每个位置的值，取最大值即为结果
class Solution { /** * @param prices: Given an integer array * @return: Maximum profit */ public int maxProfit(int[] prices) { int[] left = new int[prices.length]; int[] right = new int[prices.length]; int min = Integer.MAX_VALUE, temp = 0; for(int i = 0; i < prices.length; i++) { min = Math.min(min, prices[i]); left[i] = Math.max(prices[i] - min, temp); temp = Math.max(temp, left[i]); } int max = Integer.MIN_VALUE; int res = 0; temp = 0; for(int i = prices.length - 1; i >= 0; i--) { max = Math.max(max, prices[i]); right[i] = Math.max(max - prices[i], temp); temp = Math.max(temp, right[i]); res = Math.max(res, left[i] + right[i]); } return res; } };
