# Solution sharing, commented code ---- O(n) time and O(n) space

• ``````public class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2) return 0;//one of zero days, cannot sell
// break the problem in to subproblems, what is the max profit if i decide to buy and sell one stock on or before day i
// and the other stock after day i

int[] left = new int[prices.length];//store the max profit so far for day [0,i] for i from 0 to n
int[] right = new int[prices.length];//store the max profit so far for the days [i,n] for i from 0 to n
int minl,maxprofit,maxr,profit;
maxprofit = 0;//lower bound on profit
minl = Integer.MAX_VALUE;//minimum price so far for populating left array
for(int i = 0; i < left.length; i++){
if (prices[i] < minl) minl = prices[i];//check if this price is the minimum price so far
profit = prices[i] - minl;//get the profit of selling at current price having bought at min price so far
if (profit > maxprofit) maxprofit = profit;//if the profit is greater than the profit so far, update the max profit
left[i] = maxprofit;
}
maxprofit = 0;//reset maxprofit to its lower bound
maxr = Integer.MIN_VALUE;//maximum price so far for populating the right array
//same line of reasoning as the above
for(int i = left.length - 1; i >= 0; i--){
if (prices[i] > maxr) maxr = prices[i];
profit = maxr - prices[i];
if (profit > maxprofit) maxprofit = profit;
right[i] = maxprofit;
}
//get the best by combining the subproblems as described above
int best = 0;
for(int i = 0; i < prices.length - 1; i++){
if (left[i] + right[i+1] > best) best = left[i] + right[i+1];
}
best = best > maxprofit ? best : maxprofit;
// in total 3 passes required and 2 extra arrays of size n
return best;

}
}``````

• Thank you so much for sharing. I realize how to do it just after I saw the left[] and right[] arrays. That's extremely heuristic. I implement my own version and would like to share with you. Using your idea.

``````public class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
if(n <= 1){return 0;}
int left[] = new int[n+1]; // maximum profit gain in prices[0~left]
int right[] = new int[n+1]; // maximum profit gain in prices[right~n]

int min = prices[0];
for(int i = 1;i <= n;i++){
left[i] = Math.max(left[i-1],prices[i-1] - min);
if(min > prices[i-1])
min = prices[i-1];
}

int max = prices[n-1];
for(int i = n-1;i > 0;i--){
right[i] = Math.max(right[i+1], max-prices[i-1]);
if(max < prices[i-1])
max = prices[i-1];
}

max = 0;
for(int i = 0;i < n;i++){
if(right[i+1]+left[i] > max)
max = right[i+1]+left[i];
}

return max;
}
}``````

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