Как решить последовательное разделение динамически

#algorithm

#алгоритм

Вопрос:

В массиве arr есть число весов. arr = [1,5,3,2,4], каждое значение в arr содержит вес. n = 2, должно быть 2 блока, при разделении вес и порядок не могут быть разбиты для разделения

 Combination 1: 
block 0: [1]        max: 1
block 1: [5,3,2,4]  max: 5
----------------------------
sum of max from block 0 and 1 is 6

Combination 2: 
block 0: [1,5]      max: 5
block 1: [3,2,4]    max: 4
----------------------------
sum of max from block 0 and 1 is 9

Combination 3: 
block 0: [1,5,3]    max: 5
block 1: [2,4]      max: 4
----------------------------
sum of max from block 0 and 1 is 9

Combination 4: 
block 0: [1,5,3, 2] max: 5
block 1: [4]        max: 4
----------------------------
sum of max from block 0 and 1 is 9

So here answer is 6 from Combination 1
  

Ответ №1:

Самая сложная часть некоторых проблем — просто четко их сформулировать. Если вы можете это сделать, код практически записывается сам.

Я думаю, что постановка задачи такова: найдите минимальное значение функции (f), применяемой к каждому индексу массива (f(array, index)), где f — сумма максимальных значений двух подмассивов, образованных путем разделения входного массива по заданному индексу.

 function f(array, index) {
  let left = array.slice(0, index)
  let right = array.slice(index)
  return Math.max(...left)   Math.max(...right)
}

let array = [1, 5, 3, 2, 4]
let smallestMax = Infinity
for (let i=1; i<array.length; i  ) {
  let max = f(array, i)
  smallestMax = max < smallestMax ? max : smallestMax
}
console.log(smallestMax)  

Комментарии:

1. Хорошо сделано, очень чисто, хотя есть решение с линейным временем, но оно немного более запутанное.

Ответ №2:

У @Danh есть простое решение O (N ^ 2), но линейное время также возможно без дополнительной работы, и если у вас достаточно данных, это будет иметь огромное значение. Похоже, Дэн сделал его на JS, поэтому я постараюсь сделать то же самое. Эти циклы стиля for немного устарели, поэтому они могут быть отключены на один, но быстрый тест в консоли JS дал мне 6, как и ожидалось (после исправления ошибки копирования / вставки).

Идея состоит в том, чтобы передавать слева направо, находя максимальное значение для каждого индекса (левая сторона). Затем справа налево найдите максимальное значение для каждого индекса (справа). Затем мы смотрим на левую сторону плюс правую сторону, чтобы получить значение. В основном динамическое программирование своего рода.

 let array = [1, 5, 3, 2, 4]
let maxLeft = {}
let maxRight = {}
let max,newMax;

for (let i=0; i<array.length; i  ) {
  if (i === 0) {
    maxLeft[i] = array[i]
  } else {
    maxLeft[i] = array[i] < maxLeft[i-1] ? maxLeft[i-1] : array[i]
  }
}

for (let i=array.length - 1; i >= 0; i--) {
  if (i === array.length - 1) {
    maxRight[i] = array[i]
  } else {
    maxRight[i] = array[i] < maxRight[i 1] ? maxRight[i 1] : array[i]
  }
}

for (let i=0; i<array.length; i  ) {
  newMax = maxLeft[i]   maxRight[i   1]
  if (i === 0) {
    max = newMax 
  } else {
    maxLeft[i] = newMax < maxLeft[i-1] ? max : newMax 
  }
}
console.log(max)