Это очень распространенный вопрос программирования, и если вы хорошенько подумаете, вы поймете, что уже решали задачу с аналогичной концепцией. попробуйте вспомнить проблему «подмассив максимальной суммы».
Это похоже на то, что мы должны отслеживать максимальный продукт до всех индексов и, наконец, возвращать максимально возможный продукт.
Вопрос: для целочисленного массива
nums
найдите непрерывный подмассив в массиве (содержащий хотя бы одно число), который имеет наибольшее произведение.
Пример 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Пример 2:
Input: [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Подход грубой силы будет заключаться в том, чтобы найти все подмассивы и вычислить их продукты, а затем вернуть из них максимум. Это займет очень много времени, и мы будем обрабатывать массив без надобности много раз. Добавьте к этому, что на соревнованиях по программированию всегда будет отображаться Превышен лимит времени (TLE).
Тем не менее, это хорошее место для начала, если вы на собеседовании и пока не можете придумать оптимальный подход.
Оптимальный (одиночный обход):
- Мы проходим по массиву слева направо, отслеживая два значения, curr_max и curr_min,, эти два переменные будут отслеживать максимальный и минимальный продукт до i-го индекса.
- Теперь, если мы встретим отрицательное целое число в индексе, наблюдая, мы можем сказать, что значение curr_max будет минимальным, а значение c urr_min будет максимальным по мере их умножения. с отрицательным числом.
На заметку: то есть значение curr_min и curr_max зависит от характера текущего индекса.
Ниже я представляю псевдокод описанного выше алгоритма.
getMaxProduct(Arr[], n){ // array and it's size curr_min = Arr[0]; curr_max = Arr[0]; maxProduct = curr_max; // initialization for(i=1 to i<n){ if Arr[i] is negative: swap(curr_min, curr_max); curr_max = max of (Arr[i], curr_max*Arr[i]); curr_min = min of (Arr[i], curr_min*Arr[i]); maxPoduct = max of (maxProduct, curr_max); } our answer will be maxProduct }
Попытайтесь реализовать описанную выше логику и, если что-то не так, можете сослаться на код здесь.
Сообщите мне любые отзывы или исправления в логике или программе с вашими комментариями. Следите за обновлениями, чтобы получить больше руководств по программированию и пониманию.
Удачного кодирования.
Ссылка для тестирования проблемы: https://leetcode.com/problems/maximum-product-subarray