questEfficiencyItem.ts

// Given:
// - an array of points obtained for quests (points)
// - array of time to execute those quests (h)
// - time limit (timeForQuests)
// obtain the max score possible

// Sample input
// const h = [1, 4, 2];
// const points = [2, 3, 2];
// const timeForQuests = 4;

// Answer for sample input: 4

// O(2n) + O(n) = O(3n)
export function questEfficiencyItem(
  h: number[],
  points: number[],
  timeForQuests: number
) {
  // Create square array to store results
  const scoresArray: number[][] = [[]];

  // Loop through the points O(n)
  for (let i = 0; i < h.length; i++) {
    let timeLeft = timeForQuests;
    const pointsVal = points[i];

    // Process the row of the first iteration
    const subarray = h.slice(i, h.length);
    const scores = processRow(pointsVal, timeLeft, subarray);

    // Reset the time
    timeLeft = timeForQuests;
    scoresArray[i] = scores;
  }

  return getMaxScore(scoresArray); // TODO
}

function processRow(p: number, t: number, timeArray: number[]) {
  let pointsVal = p;
  let timeLeft = t;
  let scores: number[] = [];

  // Loop through the 'times' O(n - i)
  for (let j = 0; j < timeArray.length; j++) {
    const time = timeArray[j];

    // If there is time, execute that action
    if (time <= timeLeft) {
      // Get the the previous value for the accum. If not available, use 0.
      const add = scores[j - 1] || 0;
      scores[j] = add + pointsVal;

      // Substract the time it took
      timeLeft = timeLeft - time;

      // console.log(
      //   `Take the quest in ${time} time for ${pointsVal} points. Total score: ${
      //     scores[j]
      //   }`
      // );
    } else {
      // No action can be taken. Use the previous value for the accum. to keep going.
      const add = scores[j - 1] || 0;
      scores[j] = add;
    }
  }

  return scores;
}

// O(n)
const getMaxScore = (matrix: any[][]) => {
  let max = -1;
  // readSquaredArray(matrix);

  matrix.forEach(row => {
    // Get the last item from the row. It's the accumulation of the max.
    const accumValue = row[row.length - 1];

    if (accumValue > max) {
      max = accumValue;
    }
  });

  return max;
};

// MARK: - Utilities for debugging. Not required.

function readSquaredArray(array: any[][]) {
  array.forEach(subArray => _readArray(subArray));
}

function _readArray(array: any[]) {
  let str = "";
  array.forEach(item => (str += `${item} `));
  console.log(str, "\n");
}