Максимально возможная сумма пар не более K из двух массивов

Даны два массива arr1[] и arr2[] размеров N и M и целое число K , задача состоит в том, чтобы найти максимально возможную пару сумм из двух массивов, сумма которых не превышает K .

Примечание. Вы должны взять по одному элементу из каждого массива.

Примеры:

Input: arr1[] = {5, 4, 1, 2, 3}, arr2[] = {30, 20, 40, 10}, K = 30
Output: 25
Explanation: Maximum sum of a pair is (20 + 5) = 25 that is at most 30.

Input: toffee[] = {7, 6, 8}, candy[] = {9, 1, 5, 2, 8}, K = 5
Output: -1
Explanation: There is no such pair which have a pair sum less than or equal to 5

Подход: основная идея решения проблемы приведена ниже:

Create all the possible pairs from arr1[] and arr2[]. From these pairs find a pair whose sum is the greatest and at most equal to K.

Следуйте инструкциям, чтобы решить проблему:

• Определите переменную (скажем, sum = 0 ) для хранения суммы пары.
• Перемещаемся по массиву arr1[] от i = 0 до N :
  • Для каждого элемента массива arr1[] перейдите от j = 0 к M массива arr2[] , чтобы сформировать все возможные пары и:
    • Вычислите сумму пар arr1[i] и arr2[j].
    • Если сумма больше максимальной суммы пары до сих пор и не превышает K , обновите максимальное значение.
• После завершения цикла верните максимальное значение в качестве ответа.

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

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