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

Даны два массива X[] и Y[] длины N вместе с Q запрашивает каждый тип [L, R], который обозначает подмассив X[] от L до R. Задача состоит в том, чтобы найти максимальную сумму, которую можно получить применяя следующую операцию для каждого запроса:

• Выберите элемент из Y[].
• Добавьте множители с чередующимися знаками +ve и -ve к элементам подмассива. т. е. если выбранный элемент равен 4, то модифицируйте подмассив как {X _L + 4, X _L+1 – 8, . . . (до R ^th ) индекс}
• Удалить элемент, выбранный из Y.

Примечание. Здесь используется индексация на основе 1.

Примеры:

Input: N = 4, X[] = {1, 2, 3, 4}, Y[] = {2, 3, 5, 6}, K = 1, query = {{3, 3}}
Output: 16
Explanation:
Number of queries = 1
Sub-array from start to end index of X[]: {3}
Chose 6 from Y[] and then add alternative series of multiple of 6 = {3 + 6} = {9}. Rest of the elements except the sub-array will remain the same, Therefore, new X[] is: {1, 2, 9, 4}. The maximum sum that can obtain from 
X[] = 1+ 2+ 9+ 4 = 16

Input: N = 5, X[] = {5, 7, 2, 1, 8}, Y[] = {1, 2, 3, 4, 5}, K = 2, queries = {{1, 4}, {1, 5}}
Output: 36
Explanation:
start = 1, end = 4
The subarray = {7, 2, 1, 8}
Lets chose 1 from Y[] and add series of multiple of 1 in subarray = {7 + 1, 2 – 2, 1 + 3, 8 – 4} = {8, 0, 4, 4}.
X[]: {5, 8, 0, 4, 4}
Now, start = 1, end = 5
The subarray = {5, 8, 0, 4, 4}
lets chose 5 from Y[] and add series of multiple of 5 in subarray = {5 + 5, 8 – 10, 0 + 15,  4 – 20, 4 + 25} = {10, -2, 15, -16, 29}. Now updated X[] will be: {10, -2, 15, -16, 29}.
Overall sum of X[] is : (10 – 2 + 15 – 16 + 29) = 36. It can be verified that this sum is maximum possible.  

Интуиция: интуиция, стоящая за подходом, представлена ниже.

Let us take an example of series of multiple of an integer let say K. Then the series will be as the picture below:

Series of multiple of K

It can be seen clearly that if subarray of series is of odd length then it will contribute a positive sum in the overall sum, While series of even length will contribute negative sum to the total sum.

So the optimal idea is to add the multiples of the biggest value to the largest odd length subarray and the multiples of the smallest value to the largest even lengthed subarray.

Наивный подход:

In this method, we will do the same as mentioned in the problem statement. We will traverse on each sub-array by the given start and end indices in each query and add series of multiple of the optimal element at that current state so that our sum is maximized.

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

• Создайте ArrayList of Pairs<Start, End> DataType и инициализируйте его парами начальных и конечных индексов заданных подмассивов в запросе.
• Сортировка запросов в ArrayList в соответствии с длиной подмассивов, формальное расположение пар в порядке убывания длины.
• Сортировка Y[]. Будет удобно получить минимальный и максимальный элементы и удалить их после использования.
• Запустите цикл, сколько раз запрашиваются запросы, затем выполните следующие шаги:
  • Вычислить длину текущего подмассива. Если длина равна минимальному элементу Y[], иначе возьмите максимальный.
  • Перейдите по подмассиву и добавьте в него серию Multiple.
  • Удалите используемый элемент Y[].
• Вычислить общую сумму элементов, присутствующих в X[], пройдя массив X[]
• Выведите сумму как искомый ответ.

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

Временная сложность: O(N ² ), поскольку используется сортировка выбором
Вспомогательное пространство: O (K), поскольку используется ArrayList of Pair размера K.

Эффективный подход:

In this method, we will not be traversing on sub-array for each query. We will direct obtain the increment or decrement using a direct mathematical formula. From the intuition we can conclude that:

• If length of sub-array is odd, Then increment in overall sum of X[] will be = (((length + 1) / 2) * element)
• If the length of the sub-array is odd, Then the decrement in overall sum of X[] will be = – ((length / 2) * element)

Here element is chosen element from Y[], and length is length of sub-array in query.

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

• Создайте переменную sum и вычислите общую сумму элементов, изначально присутствующих в X[].
• Создайте список и инициализируйте его длиной подмассивов в K запросах.
• Список сортировки и массив Y[].
• Запустите цикл от конца к началу списка (формально по убыванию длины) и выполните следующие действия:
  • Если длина нечетная, добавьте (((длина+1)/2)*элемент) в переменную суммы, иначе вычтите ((длина/2)*элемент) из переменной суммы.
• Выведите значение переменной суммы.

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

Временная сложность: O(Y * log Y), поскольку сортировка выполняется по Y[].
Вспомогательное пространство: O(K), так как используется ArrayList размера K.

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам