LeetCode – Subarreglo de producto máximo (Java)

Encuentre el subarreglo contiguo dentro de un arreglo (que contenga al menos un número) que tenga el producto más grande.

Por ejemplo, dada la matriz [2,3,-2,4], el subarreglo contiguo [2,3] tiene el producto más grande = 6.

Solución Java – Programación dinámica

Esto es similar al subarreglo máximo. En lugar de suma, el signo del número afecta el valor del producto.

Al iterar la matriz, cada elemento tiene dos posibilidades: número positivo o número negativo. Necesitamos rastrear un valor mínimo, de modo que cuando se dé un número negativo, también pueda encontrar el valor máximo. Definimos dos variables locales, una rastrea el máximo y la otra rastrea el mínimo.

public int maxProduct(int[] nums) {
    int[] max = new int[nums.length];
    int[] min = new int[nums.length];
 
    max[0] = min[0] = nums[0];
    int result = nums[0];
 
    for(int i=1; i<nums.length; i++){
        if(nums[i]>0){
            max[i]=Math.max(nums[i], max[i-1]*nums[i]);
            min[i]=Math.min(nums[i], min[i-1]*nums[i]);
        }else{
            max[i]=Math.max(nums[i], min[i-1]*nums[i]);
            min[i]=Math.min(nums[i], max[i-1]*nums[i]);
        }
 
        result = Math.max(result, max[i]);
    }
 
    return result;
}

El tiempo es O (n).