Постановка задачи
Получив массив целых чисел nums, найдите в массиве непрерывный непустой подмассив с наибольшим произведением и верните произведение.
Тестовые случаи генерируются таким образом, чтобы ответ соответствовал 32-разрядному целому числу.
Подмассив — это непрерывная подпоследовательность массива.
Постановка задачи взята с: https://leetcode.com/problems/maximum-product-subarray.
Пример 1:
Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: [2, 3] has the largest product 6.Пример 2:
Input: nums = [-2, 0, -1]
Output: 0
Explanation: The result cannot be 2, because [-2, -1] is not a subarray.Ограничения:
- 1 <= nums.length <= 2 * 10^4
- -10 <= nums[i] <= 10
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.Объяснение
Подход грубой силы
Простой подход состоит в том, чтобы рассмотреть все подмассивы и вернуть максимальное произведение.
Фрагмент C++ этого подхода будет выглядеть следующим образом:
int result = arr[0];
for (int i = 0; i < n; i++) {
int mul = arr[i];
for (int j = i + 1; j < n; j++) {
result = max(result, mul);
mul *= arr[j];
}
result = max(result, mul);
}
return result;Временная сложность описанного выше подхода составляет O(N²), а пространственная сложность — O(1).
Эффективный подход
Эффективный подход аналогичен тому, что мы использовали в нашем предыдущем сообщении в блоге Максимальный подмассив. Здесь важно отметить, что массив может содержать как положительные, так и отрицательные числа, а также ноль. В задаче о максимальном подмассиве использовался алгоритм Кадане. Мы изменили этот подход и вместо этого используем три переменные, называемые max_so_far, max_ending_here и min_ending_here. Для каждого индекса максимальное число, оканчивающееся на этот индекс, будет maximum(arr[i], max_ending_here * arr[i], min_ending_here * arr[i]). Точно так же минимальное число, оканчивающееся здесь, будет минимальным из этих 3.
Сначала проверим алгоритм.
- set max_ending_here, min_ending_here and max_so_far to nums[0]
initialize temp_maximum
- loop for i = 1; i < nums.size(); i++
- temp_maximum = max(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
- min_ending_here = min(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
- max_ending_here = temp_maximum
- max_so_far = max(max_so_far, max_ending_here)
- return max_so_farДавайте проверим наши решения на C++, Golang и Javascript.
С++ решение
class Solution {
public:
int maxProduct(vector<int>& nums) {
int max_ending_here = nums[0];
int min_ending_here = nums[0];
int max_so_far = nums[0];
int temp_maximum;
for(int i = 1; i < nums.size(); i++) {
temp_maximum = max({nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here});
min_ending_here = min({nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here});
max_ending_here = temp_maximum;
max_so_far = max(max_so_far, max_ending_here);
}
return max_so_far;
}
};Голанг решение
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func maxProduct(nums []int) int {
max_ending_here, min_ending_here, max_so_far := nums[0], nums[0], nums[0]
var temp_maximum int
for i := 1; i < len(nums); i++ {
temp_maximum = max(nums[i], max(max_ending_here * nums[i], min_ending_here * nums[i]))
min_ending_here = min(nums[i], min(max_ending_here * nums[i], min_ending_here * nums[i]))
max_ending_here = temp_maximum
max_so_far = max(max_so_far, max_ending_here)
}
return max_so_far
}Javascript-решение
var maxProduct = function(nums) {
let max_ending_here = nums[0], min_ending_here = nums[0], max_so_far = nums[0];
let temp_maximum
for(let i = 1; i < nums.length; i++) {
temp_maximum = Math.max(nums[i], Math.max(max_ending_here * nums[i], min_ending_here * nums[i]));
min_ending_here = Math.min(nums[i], Math.min(max_ending_here * nums[i], min_ending_here * nums[i]));
max_ending_here = temp_maximum;
max_so_far = Math.max(max_so_far, max_ending_here)
}
return max_so_far;
};Давайте запустим наш алгоритм в пробном режиме, чтобы увидеть, как работает решение.
Input: nums = [2, 3, -2, 4]
Step 1: max_ending_here, min_ending_here, max_so_far = nums[0], nums[0], nums[0]
max_ending_here = 2
min_ending_here = 2
max_so_far = 2
initialize temp_maximum
Step 2: loop for i = 1; i < nums.size()
i < nums.size()
1 < 4
true
temp_maximum = max(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
= max(nums[1], nums[1] * 2, nums[1] * 2)
= max(3, 3 * 2, 3 * 2)
= max(3, 6, 6)
= 6
min_ending_here = min(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
= min(nums[1], nums[1] * 2, nums[1] * 2)
= min(3, 3 * 2, 3 * 2)
= min(3, 6, 6)
= 3
max_ending_here = temp_maximum
= 6
max_so_far = max(max_so_far, max_ending_here)
= max(2, 6)
= 6
i++
i = 2
Step 3: loop for i < nums.size()
i < nums.size()
2 < 4
true
temp_maximum = max(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
= max(nums[2], nums[2] * 6, nums[2] * 3)
= max(-2, -2 * 6, -2 * 3)
= max(-2, -12, -6)
= -2
min_ending_here = min(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
= min(nums[2], nums[2] * 6, nums[2] * 3)
= min(-2, -2 * 6, -2 * 3)
= min(-2, -12, -6)
= -12
max_ending_here = temp_maximum
= -2
max_so_far = max(max_so_far, max_ending_here)
= max(6, -2)
= 6
i++
i = 3
Step 4: loop for i < nums.size()
i < nums.size()
3 < 4
true
temp_maximum = max(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
= max(nums[3], nums[3] * -2, nums[3] * -12)
= max(4, 4 * -2, 4 * -12)
= max(4, -8, -48)
= 4
min_ending_here = min(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
= min(nums[3], nums[3] * -2, nums[3] * -12)
= min(4, 4 * -2, 4 * -12)
= min(4, -8, -48)
= -48
max_ending_here = temp_maximum
= 4
max_so_far = max(max_so_far, max_ending_here)
= max(6, 4)
= 6
i++
i = 4
Step 5: loop for i < nums.size()
i < nums.size()
4 < 4
false
Step 6: return max_so_far
So we return the answer as 6.Первоначально опубликовано на https://alkeshghorpade.me.
