# Java solution with just two traverses.

• Go from left to right and calculate max profit for each index (i). Go from right to left and calculate max profit for (i). Add max right profit for (i) and max left profit for (i-1) and check if it's max profit.

``````public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int lenght = prices.length;

int[] leftProfit = new int[lenght];
int leftMaxProfit = 0;
int leftMin = prices[0];
for (int i=0; i<lenght; i++) {
if (prices[i] < leftMin) leftMin = prices[i];
if (prices[i] - leftMin > leftMaxProfit) leftMaxProfit = prices[i]-leftMin;
leftProfit[i] = leftMaxProfit;
}

int maxProfit = 0;
int rightMaxProfit = 0;
int rightMax = prices[lenght-1];
for (int i=lenght-1; i>=0; i--) {
if (prices[i] > rightMax) rightMax = prices[i];
if (rightMax - prices[i] > rightMaxProfit) rightMaxProfit = rightMax - prices[i];
int currentProfit = rightMaxProfit + (i>0 ? leftProfit[i-1] : 0);
if (currentProfit > maxProfit) {
maxProfit = currentProfit;
}
}

return maxProfit;
}``````

• Could anyone tell me why "if (prices[i] < leftMin) leftMin = prices[i];" is faster than "leftMin = Math.min(leftMin, price[i])" ?

• I think it's the same.

• I have the same idea with you.
But I transform the `prices` array as `price differences`, so that it becomes similar to the problem `53 Maximum Subarray`.

Here is my code.

``````int Solution::maxProfit_split(vector<int>& prices) {
int n = prices.size();
if (n < 2) {
return 0;
}

int current_profit;

current_profit = 0;
vector<int> max_profit_left(n);
max_profit_left.front() = 0;
for (int i = 1; i < n; ++i) {  // max profit on interval [0, i]
current_profit = max(current_profit, 0);
current_profit += prices[i] - prices[i - 1];
max_profit_left[i] = max(max_profit_left[i - 1], current_profit);
}

current_profit = 0;
vector<int> max_profit_right(n);
max_profit_right.back() = 0;
for (int i = n - 2; i >= 0; --i) {    // max profit on interval [i, n - 1]
current_profit = max(current_profit, 0);
current_profit += prices[i + 1] - prices[i];
max_profit_right[i] = max(max_profit_right[i + 1], current_profit);
}

int max_profit = 0;
for (int i = 2; i <= n - 2; ++i) {  // two transactions
max_profit = max(max_profit, max_profit_left[i - 1] + max_profit_right[i]);
}
max_profit = max(max_profit, max_profit_left[n - 1]);  // only one transaction

return max_profit;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.