javascript - return the maximum accumulated profit

Question

I'm doing an exercise which i'm no being able to solve. I need to get the maximum accumulated profit by buying and selling bitcoins. I have a function(A,Y) which receive an A = array of different prices during time and a Y = fee Restrictions:

Note: If a bitcoin was bought at 0 and sold at 1, we would have ad a loss of A[1] - A[0] =7050 -7200 - Y = -200. So, that movement was not made.

Note2: You can only have 1 bitcoin at the time. To sell, you have to have bought first. To buy, you need to have nothing or sold before.

Note3: Movements need to be time consequents. You cannot buy at A[5] and sell at A[4]

Note4: If no profit cannot be made, it should return 0

complexity is O(N)

A = [7200,7050,7300,7500,7440,7200,7300,7280,7400] //expected result 550
Y = 50
A[3] - A[1] - Y = 7500 - 7050 - 50 = 400
A[8] - A[5] - Y = 7400 - 7200 - 50 = 150
result = 550 //maximum accumulated profit

This is what i have

function solution(A, Y) {

 if(A.length < 2) {
     return 0;
 }

 var minIndex = (A[0] > A[1]) ? 1 : 0;
 var minPrice = A[minIndex];

 var acum = 0;
 var i = minIndex + 1

 for (i; i< A.length-1; i++) {
    if( (A[i] - minPrice - Y) > (A[i+1] - minPrice - Y  )) {
        acum += A[i] - minPrice - Y;
        i = i+1
    } else {
        acum += A[i + 1] - minPrice - Y;
        i = i+2
    }        
    minPrice = (A[i] > A[i+1]) ? A[i+1] : A[i];        
  }     
  return acum > 0 ? acum : 0;
}

Actually i'm getting 450 but it should be 550

Answer 1

(I believe Mark_M's answer is the best here but I'll leave mine just for completeness.)

For each selling price we'd like to know the best buying price before it so we can pair that sale with the maximum accumulated before that. We can have an O(n^2) algorithm since we have to traverse back anyway.

function f(A, Y){
  let m = [0].concat(new Array(A.length - 1));

  for (let i=1; i<A.length; i++){
    let smallest = A[i-1];
    m[i] = m[i - 1];

    for (let j=i-1; j>0; j--){
      smallest = Math.min(smallest, A[j]);

      if (smallest < A[i] + Y)
        m[i] = Math.max(m[i], A[i] - smallest - Y + (m[j - 1] || 0));
    }
  }

  return m[m.length - 1];
}

var a = [7200,7050,7300,7500,7440,7200,7300,7280,7400];

console.log(f(a, 50));

Answer 2

I know you already have an answer, but I would like to propose a possible O(n) solution. The idea is that you monitor direction of price movement along with local min and max. You define a change in direction anytime the price changes direction by more than Y from the local min or max. You buy and sell on direction changes.

var A = [6000, 7200, 7050, 7040, 7045, 7041, 7039, 7300, 7500, 7490, 7480, 7501, 7440, 7200, 7300, 7280, 7400];
var A = [7200, 7050, 7300, 7500, 7440, 7200, 7300, 7280, 7400];
let Y = 50

function buysell(A, Y) {
  let direction = -1
  let min = A[0]
  let max = 0
  let total = 0

  for (let i = 1; i < A.length; i++) {
    if (direction == -1) {
      if (A[i] < min) min = A[i]
      if (A[i] - min > Y) { // only change direction if change is greater than Y
        direction = 1;
        max = A[i]
        console.log('buy at', min)
      }
    } else { // price is going up      
      if (A[i] > max) max = A[i]
      if (max - A[i] > Y) {
        total += max - min - Y
        console.log('sell at ', max)
        min = A[i]
        direction = -1
      }
    }
  }
  // buy at end if price was going up
  if (direction == 1) {
    console.log('sell at ', max)
    total += max - min - Y
  }
  return total
}
console.log("total: ", buysell(A, Y))

// Test with some edge cases:
var A = [6000, 7200,7050, 7040, 7045, 7041, 7039,7040, 7300,7500, 7490, 7480,7501, 7440,7200,7300,7280,7400];
console.log("total: ", buysell(A, Y))

var A = [ 7172, 2477, 4755, 2297, 2893, 8863 ]
console.log("total: ", buysell(A, Y))

Answer 3

It looks more complicated as it seems to be, because you need to check every single buying price with all possible selling price.

The result is a tree with this brute force approach.

This solution returns only the maximum profit with all buy/sell prices.

function maxima(array, fee) {

    function iter(prices, index, count) {
        var i = 0, profit = 0;
        if (index >= array.length) {
            if (!prices.length || prices.length % 2) {
                return;
            }
            if (prices.some((v, i, a) => i && (i % 2 ? a[i - 1] >= v : a[i - 1] < v))) {
                return;
            }
            while (i < prices.length) {
                profit += prices[i + 1] - prices[i] - fee;
                i += 2;
            }
            if (!result.length || result[0].profit < profit) {
                result = [{ profit, prices }];
            } else if (result[0].profit === profit) {
                result.push({ profit, prices });
            }
            return;
        }
        iter(prices.concat(array[index]), index + 1); // buy/sell
        iter(prices, index + 1);                      // no action
    }

    var result = [];
    iter([], 0, 0);
    return result;
}

console.log(maxima([7200, 7050, 7300, 7500, 7440, 7200, 7300, 7280, 7400], 50));

.as-console-wrapper { max-height: 100% !important; top: 0; }