Учитывая два вектора целых чисел, возможно, неравной длины, как я могу определить максимально возможный результат от накопления выбора максимума между соответствующими парами чисел между двумя векторами с дополнительными нулями, вставленными в более короткий вектор, чтобы компенсировать разницу в размере?
Например, рассмотрим следующие два вектора в качестве входных данных:
[8 1 4 5]
[7 3 6]
Варианты вставки нуля и полученной суммы:
[0 7 3 6] => Maximums: [8 7 4 6] => Sum is: 25
[7 0 3 6] => Maximums: [8 1 4 6] => Sum is: 19
[7 3 0 6] => Maximums: [8 3 4 6] => Sum is: 21
[7 3 6 0] => Maximums: [8 3 6 5] => Sum is: 22
Следовательно, в этом случае алгоритм должен вернуть 25.
Я мог бы сделать это путем грубой силы, рассчитав все перестановки размещения нулей в меньшем векторе (как только что было сделано выше), но это было бы вычислительно дорого, и наихудшее в случае, когда один вектор ровно вдвое меньше другого.
Есть ли способ вычислить ответ за линейное время, пропорциональное длине более длинного вектора, даже если векторы различаются по длине? Если нет, можем ли мы добиться большего успеха, чем количество выбранных факторных перестановок?
источник
Ответы:
Подсказка: используйте динамическое программирование. Для каждого , вычислить оптимальный способ вставки нули к префиксу длиной меньшего массива.z,l z l
источник