Максимальная сумма подмассивов в массиве, созданном после повторной конкатенации | Сет-2

Дан массив arr[] , состоящий из N целых чисел и положительного целого числа K , задача состоит в том, чтобы найти наибольшую сумму любого непрерывного подмассива в модифицированном массиве, образованном путем повторения данного массива K раз.

Примеры:

Input: arr[] = {-1, 10, 20}, K = 2
Output: 59
Explanation:
After concatenating the array twice, the array modifies to {-1, 10, 20, -1, 10, 20}. 
The subarray with the maximum sum is over the range [1, 5] i.e {10, 20, -1, 10, 20}.

Input: arr[] = {10, 20, -30, -1, 40}, K =10
Output: 391

Наивный подход: самый простой подход к решению проблемы обсуждается в наборе 1.

Эффективный подход. Описанный выше подход может быть дополнительно оптимизирован на основе следующих наблюдений:

1. Если сумма массива больше 0 , то она будет способствовать ответу. В противном случае не стоит включать все элементы массива в максимальный подмассив.
2. Предположим, что переменные maxPrefix и maxSufix хранят максимальную сумму префиксов и максимальную сумму суффиксов дважды повторяющегося массива.
3. Следовательно, подмассив максимальной суммы может быть сформирован одним из следующих способов:
   1. Добавление элементов maxSufix массива, сформированного путем объединения первых двух массивов, а затем добавление оставшихся N-2 массивов.
   2. Во-первых, добавление массивов N-2 , а затем добавление элементов maxPrefix массива, сформированного путем объединения двух последних массивов.
   3. Берем все элементы подмассива максимальной суммы дважды повторяющегося массива.

Выполните следующие шаги, чтобы решить проблему:

• Найдите сумму массива arr[] и сохраните ее в переменной, скажем, sum1 .
• Инициализируйте переменную, скажем, sum и ans как 0 , чтобы сохранить текущую максимальную сумму и ответ.
• Если K = 1 , выведите максимальную сумму подмассива массива arr[].
• В противном случае вставьте элементы массива arr[] из [0, N-1] в массив, скажем, V[] дважды.
• Найдите максимальную сумму префиксов массива V[] и сохраните ее в переменной, скажем, maxPrefix .
• Найдите максимальную сумму суффиксов массива V[] и сохраните ее в переменной, скажем, maxSufix .
• Выполните итерацию в диапазоне [0, 2*N-1] , используя переменную i , и выполните следующие шаги:
  • Измените значение суммы как max(sum + arr[i], arr[i]) и обновите значение ans как max(ans, sum).
• Если sum1 > 0, то обновить ans до максимума {ans, sum1*(K-2)+maxPrefix, sum1*(K-2)*maxSufix}.
• Наконец, после выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

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

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