[数据结构与算法]【LeetCode每日一题】——152.乘积最大子数组

一【题目类别】

• 动态规划

二【题目难度】

• 中等

三【题目编号】

• 152.乘积最大子数组

四【题目描述】

• 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
• 测试用例的答案是一个 32-位 整数。
• 子数组 是数组的连续子序列。

五【题目示例】

• 示例 1:

  • 输入: nums = [2,3,-2,4]
  • 输出: 6
    • 解释: 子数组 [2,3] 有最大乘积 6。

• 示例 2:

  • 输入: nums = [-2,0,-1]
  • 输出: 0
    • 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

六【解题思路】

• 本题的思路与【LeetCode每日一题】——剑指 Offer 42.连续子数组的最大和比较相似，只是本题做的是乘法，也就需要考虑到负负得正的情况
• 所以，我们分别维护前一次状态最大值和最小值，当遇到负数时，说明有可能发生负负得正，那么就交换最大值和最小值，这里不用担心最大值变小的问题，因为无非就两种情况
  • 最小值是一个正数，这个时候最大值变为最小值，乘一个负数，不会影响之前的最大值
  • 最小值是一个负数，这个时候最大值变为负数，很明显负负得正，相乘变大，正好可以更新
• 所以不管怎么样，都不会影响我们找到最大值
• 维护前一次状态的最大值和最小值的动态转移方程分别为：
  • $tempMax=Math.max(tempMax?nums[i],nums[i])$
  • $tempMin=Math.min(tempMin?nums[i],nums[i])$
• 每次都要记得更新最大值
• 最后返回结果即可

七【题目提示】

• $1<=nums.length<=2?10^4$
• $?10<=nums[i]<=10$
• $nums的任何前缀或后缀的乘积都保证是一个32?位整数$

八【时间频度】

• 时间复杂度：$O(n)$，其中$n$为数组大小
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

class Solution {
    public int maxProduct(int[] nums) {
        int res = Integer.MIN_VALUE;
        int tempMax = 1;
        int tempMin = 1;
        for(int i = 0;i<nums.length;i++){
            if(nums[i] < 0){
                int temp = tempMax;
                tempMax = tempMin;
                tempMin = temp;
            }
            tempMax = Math.max(tempMax * nums[i],nums[i]);
            tempMin = Math.min(tempMin * nums[i],nums[i]);
            res = Math.max(res,tempMax);
        }
        return res;
    }
}

2. C语言版

int maxProduct(int* nums, int numsSize)
{
    int res = INT_MIN;
    int tempMax = 1;
    int tempMin = 1;
    for(int i = 0;i<numsSize;i++)
    {
        if(nums[i] < 0)
        {
            int temp = tempMax;
            tempMax = tempMin;
            tempMin = temp;
        }
        tempMax = fmax(tempMax * nums[i],nums[i]);
        tempMin = fmin(tempMin * nums[i],nums[i]);
        res = fmax(res,tempMax);
    }
    return res;
}

3. Python版

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = nums[0]
        tempMax = 1
        tempMin = 1
        for i in range(0,len(nums)):
            if nums[i] < 0:
                temp = tempMax
                tempMax = tempMin
                tempMin = temp
            tempMax = max(tempMax * nums[i],nums[i])
            tempMin = min(tempMin * nums[i],nums[i])
            res = max(res,tempMax)
        return res

十【提交结果】

1. Java语言版
   

2. C语言版
   

3. Python语言版