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) { if (prices == null || prices.length == 0) return 0; int n = prices.length; int max1 = 0; int max2 = 0; int total = 0; int[] profit = new int[n]; int buy = prices[0]; int sell = prices[n-1]; for(int i = 0 ; i < n;i++){ buy= Math.min(buy,prices[i]); max1 = Math.max(max1,prices[i] - buy); profit[i] += max1; int j = n - i -1; sell = Math.max(sell,prices[j]); max2 = Math.max(max2,sell - prices[j]); profit[j] += max2; } for(int a:profit){ total = Math.max(a,total); } return total; } }