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

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

Примеры:

Input: arr[] = {2, -3, 8, -2, 5}
Output: 88
Explanation:
The required maximum product can be obtained using subarray {8, -2, 5}
Therefore, maximum product = (8 + (-2) + 5) * (8) = 88.

Input: arr[] = {-4, 1, -5, 3, 5}
Output: 40

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

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

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

• Выполните алгоритм Кадане в соответствии со следующими шагами:
  • Инициализируйте три переменные, скажем, максимальная сумма , currSum , currMax как 0 .
  • Пройдите по заданному массиву arr[] и выполните следующие шаги;
    • Обновите currSum как currSum + arr[i] и currMax как max(currMax, arr[i]) .
    • Обновите значение наибольшей суммы как max(largestSum, currMax * currSum) .
    • Если значение currSum меньше 0 , обновите значение currMax и currSum на 0 .
  • После выполнения вышеуказанных шагов верните значение наибольшей суммы как результирующее максимальное произведение суммы подмассива с его максимальным элементом.
• Инициализируйте переменную, скажем, maxSum как 0 , которая хранит максимальное произведение суммы подмассива с его максимальным элементом.
• Выполните обновленный алгоритм Кадане с заданным массивом и сохраните возвращенное значение в maxSum .
• Теперь обновите каждый элемент массива, умножив каждый элемент на (-1) , и снова выполните обновленный алгоритм Кадане с обновленным массивом, чтобы, если максимальный элемент любого подмассива был отрицательным, эта комбинация должна была учитываться.
• Обновите значение maxSum до максимального значения maxSum и значения, возвращенного предыдущим шагом.
• После выполнения вышеуказанных шагов выведите в качестве результата значение maxSum .

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

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