Разделите массив на 3 подмассива, чтобы максимизировать произведение сумм

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

Примеры:

Input: N = 4, A[] = { 1, 2, 2, 3}
Output: 18
Explanation: The optimal partitions are {1, 2}, {2}, {3}

Input: N = 3, A[] = { 3, 5, 7}
Output: 105
Explanation: There is only one possible partition {3}, {5}, {7}.

Подход: Эту проблему можно решить, используя концепцию скользящего окна и массива префиксов и суффиксов.

First, calculate the maximum product of 2 subarrays considering the size of the array from 0 to N starting from right. Now once we have the maximum product of 2 subarrays then the 3rd subarray will be on the left side.

For example, if we have calculated the maximum product of two subarrays for all the arrays starting from i to N where 0 < i < N – 1 then the third subarray will be subarray from 0 to i. And now we can calculate the maximum product of these two subarrays to get maximum product of 3 subarrays.

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

• Создайте массив суффиксов размера N .
• Создайте две переменные x и y для хранения суммы первых двух подмассивов и инициализируйте их как A[N-2] и A[N-1].
• Инициализируйте suff[N-1] как произведение x и y .
• Теперь расширьте подмассив с суммой x на 1 и продолжайте сдвигать подмассив с суммой y к подмассиву с суммой x , пока suff[i] не станет меньше x*y , и обновите suff[i] как x*y .
• Наконец, запустите цикл для вычисления максимального произведения между подмассивами от 0 до i и максимального произведения двух подмассивов от i до N , т.е. suff[i] .

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

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