题目描述

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

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

题目分析

动态规划。
假设 dp[i] 表示以位置 i 结尾的最大乘积，则 dp[i] = max(nums[i], dp[i-1] * nums[i])，直接递推就可以了。
但题目中是有负数的，存在负负得正的问题，而上面的 dp[i] 对负数是不兼容的。如果从符号入手，正数维护一套结果，负数维护一套结果，问题会变得复杂。

可以引入最小乘积来解决负数问题，max[i] 表示以位置 i 结尾的最大乘积，min[i] 表示最小乘积。如果有负数，自然会被保存在 min[i] 中，代码中无需特殊处理。
递推公式是max[i] = max(nums[i], max[i-1] * nums[i], min[i-1] * num[i]) 和 min[i] = min(nums[i], max[i-1] * nums[i], min[i-1] * num[i]) .
进一步，对于 max 和 min 这两个数组，会发现每次只用到了 i – 1，可以使用变量代替，节省空间。

时间复杂度 O(n).

Java

public int maxProduct(int[] nums) {
    int max = nums[0], min = nums[0];
    int ans = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int lastMax = max, lastMin = min;
        max = Math.max(nums[i], Math.max(lastMax * nums[i], lastMin * nums[i]));
        min = Math.min(nums[i], Math.min(lastMax * nums[i], lastMin * nums[i]));
        ans = Math.max(ans, Math.max(max, min));
    }
    return ans;
}

Kotlin

fun maxProduct(nums: IntArray): Int {
    var max = nums[0]
    var min = nums[0]
    var ans = nums[0]
    for (i in 1 until nums.size) {
        val lastMax = max
        val lastMin = min
        max = nums[i]
            .coerceAtLeast(lastMax * nums[i])
            .coerceAtLeast(lastMin * nums[i])
        min = nums[i]
            .coerceAtMost(lastMax * nums[i])
            .coerceAtMost(lastMin * nums[i])
        ans = ans.coerceAtLeast(max).coerceAtLeast(min)
    }
    return ans
}