“This is my 28th day of participating in the First Challenge 2022. For details: First Challenge 2022.”

The title

Given an array of integers, nums, find the non-empty continuous subarray with the largest product (that subarray contains at least one number) and return the product of that subarray.

The answer to the test case is a 32-bit integer.

A subarray is a continuous sequence of subarrays.

Example 1

Input: nums = [2,3,-2,4] output: 6 explanation: the subarray [2,3] has a maximum product of 6.Copy the code

Example 2

Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2 because [-2,-1] is not a subarray.Copy the code

Train of thought

This problem is similar to the largest subarray and portal ☞, but quite different;

According to the first idea in the previous article, we can get the following time complexity O(n^2) solution:

    / * * *@param {number[]} nums
     * @return {number}* /
    var maxProduct = function(nums) {
        const n = nums.length;
        if(n == 1) return nums[0];
        let max = Number.MIN_SAFE_INTEGER;

        for(let i = 0; i < n; i++) {
            let tempAns = 1;
            for(let j = i; j < n; j++) {
                // Computes the product of the current continuous subarray
                tempAns *= nums[j];
                max = Math.max(max, tempAns); }}return max;
    };
Copy the code

According to idea 2, calculate the maximum product of the subarray ending with nums[I], stored as dp[I]; Max (nums[I]* dp[I], nums[I]); But consider the following example:

[5, 6, βˆ’3, 4, βˆ’3]
Copy the code

Dp should be [5, 30, βˆ’3, 4, βˆ’3], and then you get a maximum product of 30, but obviously the final answer should be the product of all the numbers; The problem is that the negatives get the pluses and the minuses don’t get taken into account. If nums[I] is positive, and of course dp[I – 1] is also positive, then the product becomes larger; Vice versa, when nums[I] is negative, dp[i-1] is expected to be negative, and the smaller the better;

Mindp [I] = mindp[I] = mindp[I] = mindp[I] = mindp[I] = mindp Nums [I] * dp[i-1]; nums[I] * mindp[i-1]

Solution to the following

    / * * *@param {number[]} nums
     * @return {number}* /
    var maxProduct = function(nums) {
        const n = nums.length;
        if(n == 1) return nums[0];
        let max = nums[0];

        const dp = new Array(n).fill(0);
        const mindp = new Array(n).fill(0);

        dp[0] = mindp[0] = nums[0]

        for(let i = 1; i < n; i++) {
            let temp1 = nums[i] * mindp[i - 1];
            let temp2 = nums[i] * dp[i - 1];

            mindp[i] = Math.min(temp1, temp2, nums[i]);
            dp[i] = Math.max(temp1, temp2, nums[i]);

            max = Math.max(max, dp[i]);
        }
        

        return max;
    };
Copy the code

Mindp [I] = mindp[I] = mindp[I] = mindp[I] = mindp[I] = mindp[I] = mindp[I] = mindp[I] = mindp[I] = mindp[I] = minDP [I] = minDP [I] = minDP [I] = minDP [I] = minDP [I] Will not be used again; There is no need to use an array for storage, just define two variables to reduce memory usage;

Optimize memory space

    / * * *@param {number[]} nums
     * @return {number}* /
    var maxProduct = function(nums) {
        const n = nums.length;
        if(n == 1) return nums[0];
        let max = nums[0];

        let prevMin = nums[0];
        let prevMax = nums[0];

        for(let i = 1; i < n; i++) {
            let temp1 = nums[i] * prevMin;
            let temp2 = nums[i] * prevMax;

            prevMin = Math.min(temp1, temp2, nums[i]);
            prevMax = Math.max(temp1, temp2, nums[i]);

            max = Math.max(max, prevMax);
        }
        

        return max;
    };
Copy the code

summary

For this kind of, the latter result can be derived from the former result, through simple calculation of the topic, generally can use the idea of dynamic programming to deal with; When analyzing recursive formulas, careful case – by – case discussion is needed to get the correct result.

LeetCode πŸ‘‰ HOT 100 πŸ‘‰ Product maximum subarray – medium problem βœ…

Collection: LeetCode πŸ‘‰ HOT 100, will update when you are free, we support a lot, click a like πŸ‘

If you have a good solution or find something wrong with this article, please leave a comment at πŸ˜„