Минимизируйте сумму массива, заменив подмассив другим массивом

Опубликовано: 19 Сентября, 2022

Даны два массива A [] и B [] каждый размером N , задача состоит в том, чтобы минимизировать сумму массива, заменив подмассив местами.

Примеры :

Input: A[] = {10, 30, 10, 60, 20}, B[] = {40, 10, 40, 30, 10}
Output: 90
Explanation: Swap the subarray {30, 10} with {60, 20}.
The sum of array A[] = 10+30+10+30+10 = 90.
The sum of array B[] = 40+10+40+60+20 = 170.
The minimum sum = 90. 
It is the minimum possible sum an array can achieve.

Input: A[] = {10, 20, 30}, B[] = {1, 2, 3}
Output: 6

Подход : Проблема может быть решена на основе следующей идеи:

To minimize the sum of an array, we should swap such a subarray where the difference between the subarray sum is maximum i.e. for array A[] the value of (subarray of A[] – subarray of B[]) is maximum and the same for array B[]. 
The minimum between these two values will be the answer.

To implement this we can create two difference arrays and calculate the largest subarray sum from those difference arrays and subtract them from array sum.

Выполните шаги, указанные ниже, чтобы реализовать вышеуказанную идею:

  • Создайте два массива различий (скажем, t[] и s[] ) для хранения значений (A[i]-B[i]) и (B[i]-A[i]) соответственно.
  • Вычислить сумму массивов.
  • Теперь найдите максимальные суммы подмассивов из t[] и s[] , используя алгоритм Кадане.
  • Вычтите эти значения из соответствующей суммы массива, и минимум между ними и будет требуемым ответом.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ