Минимизируйте сумму произведения элементов двух массивов с одинаковым индексом, обратив подмассив одного из двух массивов

Даны два массива одинаковой длины A[] и B[] , состоящие только из положительных целых чисел, задача состоит в том, чтобы перевернуть любой подмассив первого массива так, чтобы сумма произведения элементов двух массивов с одинаковыми индексами, т. е . (A [i] * B[i]) является минимальным.

Примеры:

Input: N = 4, A[] = {2, 3, 1, 5}, B[] = {8, 2, 4, 3} 
Output: 
A[] = 1 3 2 5 
B[] = 8 2 4 3 
Minimum product is 37

Explanation: Reverse the subarray {A[0], A[2]}. Sum of product of same-indexed elements is 37, which is minimum possible.

Input: N = 3, A[] = {3, 1, 1}, B[] = {4, 5, 6} 
Output: 
A[] = 3 1 1 
B[] = 4 5 6 
Minimum product is 23

Подход: Данная проблема может быть решена с использованием метода двух указателей. Выполните следующие шаги, чтобы решить проблему:

• Объявите переменную, например total , для хранения начального произведения двух массивов.
• Объявите переменную, скажем, min , для хранения требуемого ответа.
• Объявите две переменные, скажем, first и second , для хранения начального и конечного индексов подмассива, которые нужно поменять местами, чтобы минимизировать произведение.
• Вычислите минимально возможное произведение для подмассивов нечетной длины с помощью следующих операций:
  • Пройдите массив, используя переменную, скажем, i .
  • Проверьте наличие всех подмассивов нечетной длины, установив i – 1 , скажем, left , и i + 1 , скажем, right , в качестве начального и конечного индексов подмассивов.
  • Обновите итог , вычитая a[слева] * b[слева] + a[справа] * b[справа] и добавляя a[слева] * b[справа] + a[справа] * b[слева].
  • Для каждого подмассива после обновления total проверьте, является ли он полученным минимумом или нет. Обновите и сохраните минимальный продукт соответственно.
• Точно так же проверьте все подмассивы четной длины и вычислите сумму.
• Наконец, выведите массивы и минимальную полученную сумму.

Ниже приведена реализация вышеуказанного подхода:

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