SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem is to find the maximum product of a contiguous subarray within a given array of integers. The array may contain both positive and negative integers, and the goal is to determine the maximum product possible from any contiguous subarray.

Intuition

To solve this problem, we need to keep track of both the maximum and minimum products at each position in the array. This is because a negative number can flip the sign of the product. By keeping track of both, we can ensure that we capture the maximum possible product, even when negative numbers are involved.

Approach

1. Initialization: Start by initializing three variables: maxProduct, curMin, and curMax to the value of the first element of the array.
2. Iterate Through Array: Traverse through the array starting from the second element:
   • If the current number is negative, swap curMin and curMax because multiplying by a negative number reverses the sign.
   • Update curMax to be the maximum of the current number alone or the product of curMax with the current number.
   • Update curMin to be the minimum of the current number alone or the product of curMin with the current number.
3. Update Result: Continuously update maxProduct to be the maximum of itself and curMax.

Complexity

Time Complexity:

O(n), where n is the number of elements in the array. Each element is processed once.

Space Complexity:

O(1). The space used does not depend on the input size; only a few extra variables are used.

Code

C++

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.empty()) return 0;

        int maxProduct = nums[0];
        int curMin = nums[0];
        int curMax = nums[0];

        for (int i = 1; i < nums.size(); ++i) {
            int num = nums[i];

            // When num is negative, swapping curMin and curMax is needed
            if (num < 0) {
                swap(curMin, curMax);
            }

            // Update curMax and curMin
            curMax = max(num, curMax * num);
            curMin = min(num, curMin * num);

            // Update the global maximum product
            maxProduct = max(maxProduct, curMax);
        }

        return maxProduct;
    }
};

Python

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums:
            return 0

        maxSum = nums[0]
        curMin, curMax = nums[0], nums[0]

        for i in range(1, len(nums)):
            if nums[i] < 0:
                curMin, curMax = curMax, curMin

            curMax = max(nums[i], curMax * nums[i])
            curMin = min(nums[i], curMin * nums[i])

            maxSum = max(maxSum, curMax)

        return maxSum

Java

class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) return 0;

        int maxSum = nums[0];
        int curMin = nums[0], curMax = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = curMax;
                curMax = curMin;
                curMin = temp;
            }

            curMax = Math.max(nums[i], curMax * nums[i]);
            curMin = Math.min(nums[i], curMin * nums[i]);

            maxSum = Math.max(maxSum, curMax);
        }

        return maxSum;
    }
}

JavaScript

var maxProduct = function (nums) {
    let maxSum = Math.max(...nums)
    let curMin = 1
    let curMax = 1
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 0) {
            curMin = 1
            curMax = 1
            continue
        }
        tmp = curMax * nums[i]
        curMax = Math.max(curMax * nums[i], curMin * nums[i], nums[i])
        curMin = Math.min(tmp, curMin * nums[i], nums[i])
        maxSum = Math.max(maxSum, curMax)
        console.log('curMax ', curMax)
        console.log('curMin ', curMin)
        console.log('maxSum ', maxSum)
    }

    return maxSum
};