arrays - javascript - return the maximum accumulated profit - Stack Overflow

admin管理员组

文章数量:1417712

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

plexity 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

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

plexity 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

• javascript
• arrays
• algorithm

Share Improve this question Follow edited Jun 23, 2018 at 17:10 Franco Manzur asked Jun 23, 2018 at 17:02 Franco ManzurFranco Manzur 37311 gold badge88 silver badges1919 bronze badges 4

• 1 There is an error: if i may bee A.length-1, than A[i+1] would be A[A.length]. Well, this should be undefined in Javascript. – atmin Commented Jun 23, 2018 at 17:15
• how do you know the local maximum? – Nina Scholz Commented Jun 23, 2018 at 17:26
• @NinaScholz the exercise tell me the value i should get. – Franco Manzur Commented Jun 23, 2018 at 17:31
• I think the correct answer is the one by Mark_M. – גלעד ברקן Commented Jun 24, 2018 at 11:28

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 3

It looks more plicated 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; }

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))

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

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));

本文标签： arraysjavascriptreturn the maximum accumulated profitStack Overflow