Technikai interjúk: Max Profit K Tranzakciókkal

(JavaScript nyelvű megoldás)

Egy sor pozitív egész számot kap, amelyek egyetlen részvény árfolyamát reprezentálják különböző napokon. Kapsz egy k egész számot is, amely a végrehajtható tranzakciók számát jelenti. Az egyik tranzakció abból áll, hogy egy adott napon megvásárolja a részvényt, majd egy másik napon eladja.

Írjon egy függvényt, amely k tranzakció esetén azt a maximális profitot adja vissza, amelyet a részvény vételével és eladásával elérhet (megjegyzendő, hogy egyszerre csak egy részvényt birtokolhat).

// Input: prices = [5, 11, 3, 50, 60, 90]
  //      k = 2


// Expected output: 93
  // Buy: 5, Sell: 11; Buy: 3, Sell: 90

Megoldás

Először is hozzuk létre a maxProfitWithKTransactions függvényt, amely a prices és k paramétereket veszi fel. Hozzunk létre néhány változót is.

function maxProfitWithKTransactions(prices, k) {
  
  // creating variables to store the array of previous profits,
  // the number of current row, and the array of current profits
  let prevProfits = prices.map(p => 0);
  let currentRow = 1;
  let currentProfits = [];
}

Ezután hozzunk létre egy while ciklust, és adjunk hozzá néhány új változót.

function maxProfitWithKTransactions(prices, k) {
  
  // creating variables to store the array of previous profits,
  // the number of current row, and the array of current profits
  let prevProfits = prices.map(p => 0);
  let currentRow = 1;
  let currentProfits = [];

  // while the number of current row is less than the k value
  while (currentRow <= k) {

    // assigning current profits to 0
    currentProfits = [0];

    // assigning the lagrgest potential profit to the first value of prices array with a negative sign
    let largestPotentialProfit = -prices[0];
  }
}

A while cikluson belül definiáljunk egy for ciklust, amely minden árat ellenőriz a prices tömbben, összehasonlítja a potenciális profitot a jelenlegivel, és a nagyobbat az currentProfits tömbbe tolja.

function maxProfitWithKTransactions(prices, k) {
  
  // creating variables to store the array of previous profits,
  // the number of current row, and the array of current profits
  let prevProfits = prices.map(p => 0);
  let currentRow = 1;
  let currentProfits = [];

  // while the number of current row is less than the k value
  while (currentRow <= k) {

    // assigning current profits to 0
    currentProfits = [0];

    // assigning the lagrgest potential profit to the first value of prices array with a negative sign
    let largestPotentialProfit = -prices[0];

    // iterating through the array of prices
    for (let i = 1; i < prices.length; i++) {

      // creating the variable of potential profit and assigning it to difference between the element from previous profits array and the element from prices array
      let potentialProfit = prevProfits[i] - prices[i];

      // if the value of potential profit is greater than the value of largest potential profit, reasigning the last one
      largestPotentialProfit = potentialProfit > largestPotentialProfit ? potentialProfit : largestPotentialProfit;

      // creating the variable of current profit and asigning it to the new value, if it is larger than the previous one
      let currentProfit = Math.max(prices[i] + largestPotentialProfit, currentProfits[i-1]);

      // pushing current profit value to the array of current profits
      currentProfits.push(currentProfit);
    }
  }
}

A for cikluson kívül növelnünk kell a currentRow értékét, és át kell rendelnünk a korábbi nyereséget a jelenlegiekhez. Végül a while cikluson kívül adja vissza az aktuális nyereség tömbjének utolsó értékét.

function maxProfitWithKTransactions(prices, k) {
  
  // creating variables to store the array of previous profits,
  // the number of current row, and the array of current profits
  let prevProfits = prices.map(p => 0);
  let currentRow = 1;
  let currentProfits = [];

  // while the number of current row is less than the k value
  while (currentRow <= k) {

    // assigning current profits to 0
    currentProfits = [0];

    // assigning the lagrgest potential profit to the first value of prices array with a negative sign
    let largestPotentialProfit = -prices[0];

    // iterating through the array of prices
    for (let i = 1; i < prices.length; i++) {

      // creating the variable of potential profit and assigning it to difference between the element from previous profits array and the element from prices array
      let potentialProfit = prevProfits[i] - prices[i];

      // if the value of potential profit is greater than the value of largest potential profit, reasigning the last one
      largestPotentialProfit = potentialProfit > largestPotentialProfit ? potentialProfit : largestPotentialProfit;

      // creating the variable of current profit and asigning it to the new value, if it is larger than the previous one
      let currentProfit = Math.max(prices[i] + largestPotentialProfit, currentProfits[i-1]);

      // pushing current profit value to the array of current profits
      currentProfits.push(currentProfit);
    }
    
    // increasing the value of current row
    currentRow++;

    // reasigning previous profits to current profits
    prevProfits = currentProfits;
  }
  
  // returning the last value of current profits array
  return currentProfits[currentProfits.length - 1];
}

Remélem hasznos volt számodra ez a bejegyzés :)