Это очень распространенный вопрос программирования, и если вы хорошенько подумаете, вы поймете, что уже решали задачу с аналогичной концепцией. попробуйте вспомнить проблему «подмассив максимальной суммы».

Это похоже на то, что мы должны отслеживать максимальный продукт до всех индексов и, наконец, возвращать максимально возможный продукт.

Вопрос: для целочисленного массива 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