Идеи динамического программирования: одномерные задачи, часть 2

			// иcходный массив, с монетками на кувшинках
const coins = [4, -2, 1, -1, -3];

// массив, хранящий максимальное количество монет
// при достижении i кувшинки
const maxCoins = [4, 2, 5, 4];

// в четвёртой позиции массива хранится информация про пятую кувшинку
maxCoins[4] = Math.max(maxCoins[1], maxCoins[2], maxCoins[3]) + coins[4];
		

			const getMaxCoins = (coins) => {
  // максимальное количество монет на каждой из кувшинок
  const maxCoins = [];

  // начинаем заполнение с нулевого элемента, т.е. с первой кувшинки
  // без начальных значений
  for (let i = 0; i < coins.length; i++) {
    // максимальное количество монеток, которое можно заработать
    // на предыдущих кувшинках, с которых мы можем прыгнуть на текущую
    const previousMaxCoins = [];

    // можно эти проверки выполнять в цикле
    // для первых 3-х элементов coins, массив previousMaxCoins
    // будет содержать не 3 элемента, а меньше, для остальных - 3
    if (i - 3 >= 0) previousMaxCoins.push(maxCoins[i - 3]);
    if (i - 2 >= 0) previousMaxCoins.push(maxCoins[i - 2]);
    if (i - 1 >= 0) previousMaxCoins.push(maxCoins[i - 1]);

    // количество монет на текущей кувшинке 
    // плюс в следующем if, 
    // добавляется максимальное значение с предыдущей кувшинки
    let maxCoinsInIPosition = coins[i];

    // проверка для нулевого элемента
    // когда массив previousMaxCoins будет пустой
    // и Math.max(...[]) вернет -Infinity
    if (previousMaxCoins.length > 0) {
      maxCoinsInIPosition += Math.max(...previousMaxCoins);
    }

    // здесь проверяем условие, чтобы у кузнечика
    // не было отрицательное количество монеток
    // можно было вот так 
    // maxCoinsInIPosition = Math.max(maxCoinsInIPosition, 0);
    maxCoinsInIPosition = maxCoinsInIPosition < 0 ? 0 : maxCoinsInIPosition;
    
    maxCoins.push(maxCoinsInIPosition);
  }

  // в 0 элементе хранится значение для первой кувшинки
  // массив заполнен на maxCoins.length значений
  // от 0 до maxCoins.length
  return maxCoins[maxCoins.length - 1];
}

console.log(getMaxCoins([4, -2, 1, -1, -3]));
		

			const getMaxCoinsPath = (coins) => {
  const maxCoins = [];
  for (let i = 0; i < coins.length; i++) {
    const previousMaxCoins = [];

    if (i - 3 >= 0) previousMaxCoins.push(maxCoins[i - 3]);
    if (i - 2 >= 0) previousMaxCoins.push(maxCoins[i - 2]);
    if (i - 1 >= 0) previousMaxCoins.push(maxCoins[i - 1]);

    let maxCoinsInIPosition = coins[i];
    if (previousMaxCoins.length > 0) {
      maxCoinsInIPosition += Math.max(...previousMaxCoins);
    }

    maxCoinsInIPosition = maxCoinsInIPosition < 0 ? 0 : maxCoinsInIPosition;
    maxCoins.push(maxCoinsInIPosition);
  }

  // до этого момента код тот же, что и в предыдущем примере
  return findPath(maxCoins);
}

const findPath = (maxCoins) => {
  // последняя кувшинка всегда в пути, по условию задачи
  const path = [maxCoins.length - 1];

  let maxCoinsPreviousPosition = maxCoins.length - 1;
  while (maxCoinsPreviousPosition >= 0) {
    // 0 для первых 3-х элементов
    const previousPositionShift =
      maxCoinsPreviousPosition - 3 > 0 ? maxCoinsPreviousPosition - 3 : 0;

    // для текущего примера [-1, -1, 4, -2, 1, -1, -3]
    // диапазон previousPositionShift maxCoinsPreviousPosition
    // будет принимать значения
    // 3 6
    // 1 4
    // 0 2
    // 0 0
    // slice не включает последний элемент, при использовании 0, 0 вернется
    // пустой массив

    // отрезаем предыдущие 3(или меньше) элементов, для поиска максимума
    const previousCoinsValues = maxCoins.slice(
      previousPositionShift,
      maxCoinsPreviousPosition
    );
    
    // когда previousCoinsValues - пустой массив, поиск пути завершен
    if (previousCoinsValues.length === 0) break;
    
    const previousMaxCoinValue = Math.max(...previousCoinsValues);
    
    // если несколько одинаковых значений, то находим только одно из них
    // previousMaxCoinPosition может содержать значение от 0 до 2
    const previousMaxCoinPosition =
      previousCoinsValues.indexOf(previousMaxCoinValue);

    maxCoinsPreviousPosition = previousMaxCoinPosition
      + previousPositionShift;

    path.push(maxCoinsPreviousPosition);
  }

  // искали путь с конца, для окончательного ответа нужно его инвертировать
  return path.reverse();
}

// путь - [0, 2, 4, 6]
console.log(getMaxCoinsPath([-1, -1, 4, -2, 1, -1, -3]));
		

			const getMaxCoinsPath = (coins) => {
  const maxCoins = [];
  for (let i = 0; i < coins.length; i++) {
    const previousMaxCoins = [];

    if (i - 3 >= 0) previousMaxCoins.push(maxCoins[i - 3]);
    if (i - 2 >= 0) previousMaxCoins.push(maxCoins[i - 2]);
    if (i - 1 >= 0) previousMaxCoins.push(maxCoins[i - 1]);

    let maxCoinsInIPosition = coins[i];
    let pathToMaxCoins = null;

    if (i !== 0) {
      // позиция в previousCoins с максимальным количеством монеток
      let maxCoinsPositionInPrevious = 0;
      let maxCoins = previousMaxCoins[0].coins;

      for (let j = 1; j < previousMaxCoins.length; j++) {
        if (maxCoins < previousMaxCoins[j].coins) {
          maxCoins = previousMaxCoins[j].coins;
          maxCoinsPositionInPrevious = j;
        }
      }

      // путь до предыдущего элемента, с набором максимума монеток
      pathToMaxCoins = previousMaxCoins[maxCoinsPositionInPrevious].path;
      
      // в maxCoinsInIPosition исходное значение монеток на кувшинке i
      // coins[i]
      // плюс максимальное значение на предыдущей кувшинке, с которой можем
      // прыгнуть на нее
      maxCoinsInIPosition += maxCoins;
    } else {
      // для первого элемента - пустой путь
      pathToMaxCoins = [];
    }

    maxCoinsInIPosition = maxCoinsInIPosition < 0 ? 0 : maxCoinsInIPosition;
    // добавляем i к пути, для текущего элемента
    maxCoins.push(
      { coins: maxCoinsInIPosition, path: [...pathToMaxCoins, i] }
    );
  }

  // просто возвращаем путь для последнего элемента
  return maxCoins[maxCoins.length - 1].path;
}

// [0, 2, 4, 6]
console.log(getMaxCoinsPath([-1, -1, 4, -2, 1, -1, -3]));
		

			const longestSubsequence = [1];
		

			const lengthOfLongestIncreasingSubsequence = (nums) => {
    // массив, содержащий длину максимальной подпоследовательности
    // в позиции соответствующего элемента,
    // т.е. longestSubsequence[0] соответствует максимальной длине для 
    // nums[0]
    const longestSubsequence = [1];
    
    // 0-й элемент уже обработали через установку начального значения,
    for (let i = 1; i < nums.length; i++) {
        // находим в эту переменную длину максимальной подпоследовательности,
        // в которую можем добавить текущий элемент
        let maxPreviousSubsequence = 0;
        
        // проходим все элементы левее текущего - i элемента
        // находим те, которые меньше текущего значение - nums[i]
        // и находим наибольшую подпоследовательность,
        // предыдущие значения хранятся в longestSubsequence[j]
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i] &&
                longestSubsequence[j] > maxPreviousSubsequence) {
                maxPreviousSubsequence = longestSubsequence[j];
            }
        }
        
        // после обработки очередного элемента,
        // длина подпоследовательности увеличивается на 1
        longestSubsequence.push(maxPreviousSubsequence + 1);
    }
    
    // ответ может быть в любой позиции, и это просто максимальное число
    return Math.max(...longestSubsequence);
};

// максимальная длина - 4
console.log(lengthOfLongestIncreasingSubsequence([1, 5, 3, 6, 4, 5, 2]));
		

			const getLongestIncreasingSubsequence = (nums) => {
    const longestSubsequenceInPosition = [1];
    const previousIndexOfLongestSubsequence = [-1];
    
    for (let i = 1; i < nums.length; i++) {
        let maxPreviousSubsequence = 0;

        // если внутри следующего for, по предыдущим элементам,
        // не войдем в if ни один раз
        // значит предыдущего элемента нет
        // и надо проставить значение по умолчанию: -1
        previousIndexOfLongestSubsequence[i] = -1;
        
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i] &&
                longestSubsequenceInPosition[j] > maxPreviousSubsequence) {
                maxPreviousSubsequence = longestSubsequenceInPosition[j];
                
                // если вошли в этот if
                // значит в позиции j нужный предыдущий элемент
                previousIndexOfLongestSubsequence[i] = j;
            }
        }
        
        longestSubsequenceInPosition.push(maxPreviousSubsequence + 1);
    }
    
    // для рассматриваемого примера [5, 1, 5, 3, 6, 4, 5, 2]
    // массив с максимальной подпоследовательностью в позиции
    // longestSubsequenceInPosition [1, 1, 2, 2, 3, 3, 4, 2]
    // индекс предыдущего элемента, для максимальной подпоследовательности
    // previousIndexOfLongestSubsequence [-1,-1,1, 1, 2, 3, 5, 1]
    
    const lengthOfLongestSubsequence =
      Math.max(...longestSubsequenceInPosition);
    
    // позиция окончания максимальной подпоследовательности
    const lastIndexOfLongestSubsequence =
      longestSubsequenceInPosition.indexOf(lengthOfLongestSubsequence);

    const longestSubsequence = [];
	let currentElementOfSubsequence = lastIndexOfLongestSubsequence;
	
    // идем по массиву previousIndexOfLongestSubsequence,
    // находя предыдущие элементы,
    // начиная с lastIndexOfLongestSubsequence,
    // когда достигнем -1 значения, то предыдущего элемента нет
    while (currentElementOfSubsequence !== -1) {
        longestSubsequence.push(nums[currentElementOfSubsequence]);
        
        currentElementOfSubsequence =
          previousIndexOfLongestSubsequence[currentElementOfSubsequence];
    }
    
    // массив, как и в предыдущей задаче, инвертирован
    return longestSubsequence.reverse();
};

// максимальная подпоследовательность - [1, 3, 4, 5]
console.log(getLongestIncreasingSubsequence([5, 1, 5, 3, 6, 4, 5, 2]));
		

			const gameResultForStartPlayer = 
  [false, true, false, true, false, true, false, true, false, true];
		

			const divisorGame = (n) => {
  // рассмотренный выше массив, для результата на текущем ходе игрока
  const gameResultForStartPlayer = [false];
  
  for (let i = 2; i <= n; i++) {
    let resultOfIGame = false;
    
    // ищем все делители, без оптимизаций - цикла до Math.sqrt(i), например
    for (let divisor = 1; divisor < i; divisor++) {
      // если будет false хотя бы в одной позиции gameResultForStartPlayer,
      // для числа, которое останется противнику,
      // значит оппонент проигрывает
      // и в текущую позицию в gameResultForStartPlayer, добавим true
      if (i % divisor == 0 &&
          gameResultForStartPlayer[i - divisor - 1] == false) {
        resultOfIGame = true;
        break;
      }
    }
    
    gameResultForStartPlayer.push(resultOfIGame);
  }

  // в 0 позиции храним значение для 1 числа, в n-1 для n-го числа
  return gameResultForStartPlayer[n - 1];
};