leetcode之152乘积最大子数组Golang

题目描述

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

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

示例 2:

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

算法

本题我们采用动态规划的方法

对于数组中的任意一个数，它有3种状态，为0，为正数，为负数

当我们要求乘积最大的子数组的时候，其实就是对于每一个数字，将他作为子数组的最后一个元素的时候，找到乘积最大的这个子数组

对于每一个元素，我们保存他作为子数组最后一个元素的条件下所能够取得的乘积的最大值和最小值

• 如果元素的值为0，那么他的最大值和最小值都是0
• 如果元素的值大于0
  • 我们用该元素乘以它前一个元素所得乘积的最大值，将这个新乘积和该元素比较，将更大的数作为当前元素作为子数组最后一个元素所能取得乘积的最大值
  • 我们用该元素乘以它前一个元素所得乘积的最小值，将这个新乘积和该元素比较，将更小的数作为当前元素作为子数组最后一个元素所能取得乘积的最小值
• 如果元素的值小于0
  • 我们用该元素乘以它前一个元素所得乘积的最小值，将这个新乘积和该元素比较，将更大的数作为当前元素作为子数组最后一个元素所能取得乘积的最大值
  • 我们用该元素乘以它前一个元素所得乘积的最大值，将这个新乘积和该元素比较，将更小的数作为当前元素作为子数组最后一个元素所能取得乘积的最小值
• 我们已经求出所有元素作为子数组最后一个元素所能取得乘积的最大值，然后取这些最大值中的最大值返回就可以了

代码

go

func maxProduct(nums []int) int {
	max := make([]int, len(nums))
	min := make([]int, len(nums))
	res := nums[0]
	max[0] = nums[0]
	min[0] = nums[0]
	for index := 1; index < len(nums); index++ {
		if nums[index] == 0 {
			max[index] = 0
			min[index] = 0
		} else {
			var tmpMax int
			var tmpMin int
			if nums[index] > 0 {
				tmpMax = nums[index] * max[index-1]
				tmpMin = nums[index] * min[index-1]
			} else {
				tmpMax = nums[index] * min[index-1]
				tmpMin = nums[index] * max[index-1]
			}
			if tmpMax > nums[index] {
				max[index] = tmpMax
			} else {
				max[index] = nums[index]
			}
			if tmpMin < nums[index] {
				min[index] = tmpMin
			} else {
				min[index] = nums[index]
			}
		}
		if res < max[index] {
			res = max[index]
		}
	}
	return res
}

c++

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<int> maxVec(nums.size());
        vector<int> minVec(nums.size());
        maxVec[0]=nums[0];
        minVec[0]=nums[0];
        int res=nums[0];
        for(size_t index=1;index<nums.size();index++){
            if(nums[index]==0){
                maxVec[index]=0;
                minVec[index]=0;
            }else{
                int tmpMax=0,tmpMin=0;
                if(nums[index]>0){
                    tmpMax=nums[index]*maxVec[index-1];
                    tmpMin=nums[index]*minVec[index-1];
                }else{
                    tmpMax=nums[index]*minVec[index-1];
                    tmpMin=nums[index]*maxVec[index-1];
                }
                // 更新maxVec和minVec
                maxVec[index]=tmpMax>nums[index]?tmpMax:nums[index];
                minVec[index]=tmpMin<nums[index]?tmpMin:nums[index];
            }
            res=res>maxVec[index]?res:maxVec[index];
        }
        return res;
    }
};