javascript - 返回最大累计利润

Question

我正在做一个我无法解决的练习。我需要通过买卖比特币来获得最大的累计利润。我有一个函数(A，Y)，它在一段时间内接收一个 A = 不同价格的数组和一个 Y = 费用 限制:

注意:如果比特币以 0 的价格买入并以 1 的价格卖出，我们将损失 A[1] - A[0] =7050 -7200 - Y = -200。因此，没有进行该运动。

注意2:您当时只能拥有1个比特币。要卖，你必须先买。要购买，您需要之前一无所有或已售出。

注3:运动需要是时间的结果。您不能在 A[5] 买入并在 A[4] 卖出

注4:如果不能盈利，则返回0

复杂度为 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

这是我的

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

实际上我得到了 450 但它应该是 550

Answer 1

它看起来更复杂，因为你需要检查每一个买入价和所有可能的卖出价。

结果是采用这种蛮力方法的树。

此解决方案仅返回所有买入/卖出价格的最大利润。

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