Найдите минимальную сумму пары, выбрав элемент из 2-го массива с индексом больше, чем 1-й массив

Учитывая два массива A[] и B[] размера N каждый, задача состоит в том, чтобы минимизировать A[i] + B[j] так, чтобы j ≥ i .

Примеры:

Input: A[] = {34, 12, 45, 10, 86, 39, 77},  
           B[] = {5, 42, 29, 63, 30, 33, 20}
Output: 30
Explanation: For minimizing the sum, take i = 3 and j = 6.

Input: A[] = {34, 17, 45, 10, 19},  
           B[] = {2, 13, 7, 11, 16}
Output: 21
Explanation: For minimizing the sum, take both i and j = 3.

Наивный подход . Наивный подход к решению этой проблемы заключается в использовании 2 циклов for, одного для перебора A[] и другого для перебора B[] . Просто проверьте и сравните все возможности, чтобы минимизировать сумму.

Ниже приведена реализация описанного выше наивного подхода.

Временная сложность: O(N ² )
Вспомогательное пространство: О(1)

Эффективный подход. Эффективный способ решить эту проблему — создать массив, содержащий минимальное значение до i -го индекса от заднего конца B[] . Затем пройдите через A[] и для каждого индекса минимальная сумма будет суммой минимума от начала A[] и минимума от конца B[] до этого индекса. Выполните следующие шаги, чтобы решить данную проблему.

• Создать массив для хранения минимального значения из заднего конца B[] для каждого индекса.
• Поскольку в последнем индексе есть только одно возможное значение, присвойте последнее значение индекса массива B[] последнему индексу нового массива.
• Теперь пройдите B[] с задней стороны и сравните текущее значение индекса (скажем, i) в B[] с индексом (i+1) в новом массиве и сохраните минимальное значение этих двух в i -м индексе массива. только что созданный массив.
• Теперь выполните итерацию по элементам X и посмотрите на этот индекс в новом массиве . Поскольку этот индекс в новом массиве является наименьшим возможным значением, присутствующим в B[] для i и выше.

Ниже приведена реализация описанного выше эффективного подхода.

Сложность времени: НА)
Вспомогательное пространство: НА)