Why re-using code for #121 may fail here. Explanation and thinking process included.

• My first thought is to re-use the code that is used to solve #121, in a big for loop. It is however an O(n^2) solution and exceeds the time limits. (see explanation below, namely the calc function at the bottom and the for loop that's commented out)

``````var maxProfit = function(prices) {

if(prices.length < 2) {
return 0;
}
if(prices.length == 2) {
return Math.max(0, prices[1] - prices[0]);
}

var maxProfit = 0;
var frontProfit = [];
var backProfit = [];
var sellPrice;

// The reason the approach is not efficient is because it calculates many values that has been calculated.
// For example, to calculate frontProfit[10], frontProfit[9] and [8] and so on till [0] will ALL be calculated again,
// and these side-product values will not be stored again because they are written in the array already.
// The complexity is O(n^2), inefficient
// for(var i = 0; i < prices.length; i++) {
//     // var pro = calc(prices, 0, i) + calc(prices, i, prices.length);
//     // maxProfit = Math.max(pro, maxProfit);
//     frontProfit[i] = calc(prices, 0, i);
//     backProfit[i] = calc(prices, i, prices.length);
// }

// use an index i to divide the entire array into two parts: front and back
// calculate the max profit using 1 (or fewer) transaction between day 0 thru day i (variable)
// store the results in another array

// for example
// array:   1 4 2   or  1  15   4 100  90 100
// front:   0 3 3   or  0  14  14  99  99  99
// back:    3 0 0   or 99  96  96  10  10   0
// max=f+b: 3 3 3   or 99 110 110 109 109  99
// Note: front[0] and back[len-1] are pre-set to 0

var maxDiff = 0;
frontProfit[0] = 0;

for(var i = 1; i < prices.length; i++) {
frontProfit[i] = frontProfit[i-1];
var diff = prices[i] - buyPrice;
if(diff > maxDiff) {
maxDiff = diff;
sellPrice = prices[i];
frontProfit[i] = maxDiff;
}
// decreasing interval
if(diff < 0) {
frontProfit[i] = frontProfit[i-1];
}
}

// calculate the max profit using 1 (or fewer) transaction between day i (variable) thru last day
// store the results in another array
maxDiff = 0;
backProfit[prices.length-1] = 0;

for(var i = prices.length - 2; i >= 0; i--) {
backProfit[i] = backProfit[i+1];
var diff = buyPrice - prices[i]; // note the order is different
// next price is higher (by at least maxDiff), then update sellPrice
if(diff > maxDiff) {
maxDiff = diff;
sellPrice = prices[i];
backProfit[i] = maxDiff;
}
// next price is lower : decreasing interval
if(diff < 0) {
backProfit[i] = backProfit[i+1];
}
}

for(var j = 0; j < prices.length; j++) {
maxProfit = Math.max((frontProfit[j] + backProfit[j]), maxProfit);
}

return maxProfit;

};

/*
var calc = function(arr, start, end) {
// end is excluded
var prices = arr.slice(start, end);
if(prices.length < 2) {
return 0;
}

var maxDiff = -1;
var sellPrice;

for(var i = 0; i < prices.length; i++) {
var diff = prices[i] - buyPrice;
// next price is higher (by at least maxDiff), then update sellPrice
if(diff > maxDiff) {
maxDiff = diff;
sellPrice = prices[i];
}
// next price is lower : decreasing interval
if(diff < 0) {
}
}

if(maxDiff > -1) {
return maxDiff;
} else {
return 0;
}
}
*/
``````

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