Leetcode 乘积最大子数组

2023-04-28

乘积最大子数组

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

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

题解思路

如果按照常规动态规划解法,维护一个dp数组记录以nums中每个元素为结尾的乘积最大连续子数组的乘积,会出现错误,因为如果考虑[-2, 3, -4]这样的用例,会发现按照上述方法的答案为3,而正确结果应该为-2 * 3 * -4 = 24. 因为当前位置的最优解未必是由前一个位置的最优解转移得到的

当 前一个位置是一个很小的负数时,如果当前元素也是负数,那么就可以得到一个很大的值,而这个值很可能就是我们要找的解。而在上一段提到的方法中,这个解被忽略掉了。

考虑到一个绝对值很大的负数也是有利用价值的,我们应该同时维护一个dp数组来存储以nums中某个元素为结尾的子串的乘积的最小值。而以当前元素为结尾的连续子序列的乘积的最大值,可以是
当前元素 * 以上一个元素为结尾的最长子序列的乘积的最大值 亦可以是
当前元素 * 以上一个元素为结尾的最长子序列的乘积的最小值
两种情况分别对应当前元素为正和为负的情况。

状态转移方程可以写成:
状态转移方程

代码

func maxProduct(nums []int) int {
    // maxF和minF来维护加上当前元素的最大和最小值
    maxF, minF := nums[0], nums[0]
    result := -0x80000000
    result = findMax(maxF,result)
    for i:= 1; i< len(nums); i++ {
        ma, mi := maxF,minF
        maxF = findMax(ma * nums[i], findMax(mi * nums[i], nums[i]))
        minF = findMin(ma * nums[i], findMin(mi * nums[i], nums[i]))
        result = findMax(maxF, result)
    }
    return result
}

func findMax(a int, b int) int {
    if a > b {
        return a
    }else{
        return b
    }
}

func findMin(a int, b int) int {
    if a < b {
        return a
    }else{
        return b
    }
}

性能:

执行用时:8 ms, 在所有 Go 提交中击败了33.84%的用户
内存消耗:3.2 MB, 在所有 Go 提交中击败了43.59%的用户
通过测试用例:190 / 190

评论