本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

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

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

请注意，一个只包含一个元素的数组的乘积是这个元素的值。

示例 1:

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

示例 2:

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

提示:

  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10
  • nums 的任何子数组的乘积都 保证 是一个 32-位 整数

解法 动态规划

本题是 [[LeetCode 53. 最大子数组和【动态规划】简单]] 的乘法版本，推荐先完成 53 题。

寻找子问题

例如 n u m s = [ − 2 , 1 , − 3 , 4 ] nums=[−2,1,−3,4] nums=[−2,1,−3,4] ，讨论右端点为 n u m s [ 3 ] = 4 nums[3]=4 nums[3]=4 的子数组的最大乘积：

  • 4 4 4 单独组成一个子数组。
  • 4 4 4 和前面的子数组拼起来，也就是在右端点为 n u m s [ 2 ] = − 3 nums[2]=−3 nums[2]=−3 的乘积最大子数组之后添加 4 4 4 。

又例如 n u m s = [ − 2 , 1 , − 3 , − 4 ] nums=[−2,1,−3,−4] nums=[−2,1,−3,−4] ，讨论右端点为 n u m s [ 3 ] = − 4 nums[3]=−4 nums[3]=−4 的子数组的最大乘积：

  • − 4 −4 −4 单独组成一个子数组。
  • − 4 −4 −4 和前面的子数组拼起来，由于 − 4 −4 −4 是负数，要想得到最大的乘积，根据负负得正，我们可以在右端点为 n u m s [ 2 ] = − 3 nums[2]=−3 nums[2]=−3 的乘积最小子数组之后添加 − 4 −4 −4 。
状态定义与状态转移方程

上面两个例子启发我们，需要在遍历 n u m s nums nums 的同时，维护两个信息：

  • 右端点下标为 i i i 的子数组的最大乘积，记作 f m a x [ i ] f_{max}[i] fmax​[i] 。
  • 右端点下标为 i i i 的子数组的最小乘积，记作 f m i n [ i ] f_{min}[i] fmin​[i] 。

设 x = n u m s [ i ] x=nums[i] x=nums[i] ，分类讨论：

  • x x x 单独组成一个子数组，那么 f m a x [ i ] = x f_{max}[i]=x fmax​[i]=x 。
  • x x x 和前面的子数组拼起来，也就是在右端点下标为 i − 1 i−1 i−1 的乘积最大子数组之后添加 x x x ，那么 f m a x [ i ] = f m a x [ i − 1 ] ⋅ x f_{max}[i]=f_{max} [i−1]⋅x fmax​[i]=fmax​[i−1]⋅x ；也可以在右端点下标为 i − 1 i−1 i−1 的乘积最小子数组之后添加 x x x ，那么 f m a x [ i ] = f m i n [ i − 1 ] ⋅ x f_{max}[i]=f_{min}[i−1]⋅x fmax​[i]=fmin​[i−1]⋅x 。

把这两种都算一下，这样我们就无需判断 x x x 到底是正还是负了。

三种情况取最大值，得
f m a x [ i ] = max ⁡ ( f m a x [ i − 1 ] ⋅ x , f m i n [ i − 1 ] ⋅ x , x ) f_{max}[i]=\max(f_{max}[i−1]⋅x,f_{min}[i−1]⋅x,x) fmax​[i]=max(fmax​[i−1]⋅x,fmin​[i−1]⋅x,x)
同理得
f m i n [ i ] = min ⁡ ( f m a x [ i − 1 ] ⋅ x , f m i n [ i − 1 ] ⋅ x , x ) f_{min}[i]=\min(f_{max}[i−1]⋅x,f_{min}[i−1]⋅x,x) fmin​[i]=min(fmax​[i−1]⋅x,fmin​[i−1]⋅x,x)
由于以 n u m s [ 0 ] nums[0] nums[0] 为右端点的子数组乘积只能是 n u m s [ 0 ] nums[0] nums[0] ，所以初始值为 f m a x [ 0 ] = f m i n [ 0 ] = n u m s [ 0 ] f_{max}[0]=f_{min}[0]=nums[0] fmax​[0]=fmin​[0]=nums[0]这是一种初始化的方法，下文会讲另外一种。

答案为 max ⁡ ( f m a x ) \max(f_{max}) max(fmax​) 。

写法1
class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] fMax = new int[n];
        int[] fMin = new int[n];
        fMax[0] = fMin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            int x = nums[i];
            // 把 x 加到右端点为 i-1 的（乘积最大/最小）子数组后面，
            // 或者单独组成一个子数组，只有 x 一个元素
            fMax[i] = Math.max(Math.max(fMax[i - 1] * x, fMin[i - 1] * x), x);
            fMin[i] = Math.min(Math.min(fMax[i - 1] * x, fMin[i - 1] * x), x);
        }
        return Arrays.stream(fMax).max().getAsInt();
    }
}

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> f_max(n), f_min(n);
        f_max[0] = f_min[0] = nums[0];
        for (int i = 1; i < n; i++) {
            int x = nums[i];
            // 把 x 加到右端点为 i-1 的（乘积最大/最小）子数组后面，
            // 或者单独组成一个子数组，只有 x 一个元素
            f_max[i] = max({f_max[i - 1] * x, f_min[i - 1] * x, x});
            f_min[i] = min({f_max[i - 1] * x, f_min[i - 1] * x, x});
        }
        return ranges::max(f_max);
    }
};

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        f_max = [0] * n
        f_min = [0] * n
        f_max[0] = f_min[0] = nums[0]
        for i in range(1, n):
            x = nums[i]
            # 把 x 加到右端点为 i-1 的（乘积最大/最小）子数组后面，
            # 或者单独组成一个子数组，只有 x 一个元素
            f_max[i] = max(f_max[i - 1] * x, f_min[i - 1] * x, x)
            f_min[i] = min(f_max[i - 1] * x, f_min[i - 1] * x, x)
        return max(f_max)

func maxProduct(nums []int) int {
    n := len(nums)
    fMax := make([]int, n)
    fMin := make([]int, n)
    fMax[0], fMin[0] = nums[0], nums[0]
    for i := 1; i < n; i++ {
        x := nums[i]
        // 把 x 加到右端点为 i-1 的（乘积最大/最小）子数组后面，
        // 或者单独组成一个子数组，只有 x 一个元素
        fMax[i] = max(fMax[i-1]*x, fMin[i-1]*x, x)
        fMin[i] = min(fMax[i-1]*x, fMin[i-1]*x, x)
    }
    return slices.Max(fMax)
}

impl Solution {
    pub fn max_product(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut f_max = vec![0; n];
        let mut f_min = vec![0; n];
        f_max[0] = nums[0];
        f_min[0] = nums[0];
        for i in 1..n {
            let x = nums[i];
            // 把 x 加到右端点为 i-1 的（乘积最大/最小）子数组后面，
            // 或者单独组成一个子数组，只有 x 一个元素
            f_max[i] = x.max(f_max[i - 1] * x).max(f_min[i - 1] * x);
            f_min[i] = x.min(f_max[i - 1] * x).min(f_min[i - 1] * x);
        }
        *f_max.iter().max().unwrap()
    }
}

var maxProduct = function(nums) {
    const n = nums.length;
    const fMax = new Array(n);
    const fMin = new Array(n);
    fMax[0] = fMin[0] = nums[0];
    for (let i = 1; i < n; i++) {
        const x = nums[i];
        // 把 x 加到右端点为 i-1 的（乘积最大/最小）子数组后面，
        // 或者单独组成一个子数组，只有 x 一个元素
        fMax[i] = Math.max(fMax[i - 1] * x, fMin[i - 1] * x, x);
        fMin[i] = Math.min(fMax[i - 1] * x, fMin[i - 1] * x, x);
    }
    return Math.max(...fMax);
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))
#define MIN(a, b) ((b) < (a) ? (b) : (a))

int maxProduct(int* nums, int numsSize) {
    int* f_max = malloc(numsSize * sizeof(int));
    int* f_min = malloc(numsSize * sizeof(int));
    f_max[0] = f_min[0] = nums[0];
    int ans = nums[0];

    for (int i = 1; i < numsSize; i++) {
        int x = nums[i];
        // 把 x 加到右端点为 i-1 的（乘积最大/最小）子数组后面，
        // 或者单独组成一个子数组，只有 x 一个元素
        f_max[i] = MAX(MAX(f_max[i - 1] * x, f_min[i - 1] * x), x);
        f_min[i] = MIN(MIN(f_max[i - 1] * x, f_min[i - 1] * x), x);
        ans = MAX(ans, f_max[i]);
    }

    free(f_max);
    free(f_min);
    return ans;
}

复杂度分析：

  • 时间复杂度： O ( n ) O(n) O(n) ，其中 n n n 是 n u m s nums nums 的长度。
  • 空间复杂度： O ( n ) O(n) O(n) 。
写法2 空间优化

由于计算 f m a x [ i ] f_{max}[i] fmax​[i] 和 f m i n [ i ] f_{min}[i] fmin​[i] 只会用到 f m a x [ i − 1 ] f_{max}[i - 1] fmax​[i−1] 和 f m i n [ i − 1 ] f_{min}[i - 1] fmin​[i−1] ，不会用到更早的状态，所以可用两个变量 f m a x f_{max} fmax​ 和 f m i n f_{min} fmin​ 滚动计算。

状态转移方程简化为：
f m a x = max ⁡ ( f m a x ⋅ x , f m i n ⋅ x , x ) f_{max} = \max( f_{max} \cdot x, f_{min} \cdot x, x) fmax​=max(fmax​⋅x,fmin​⋅x,x)
f m i n = min ⁡ ( f m a x ⋅ x , f m i n ⋅ x , x ) f_{min} = \min( f_{max} \cdot x, f_{min} \cdot x, x) fmin​=min(fmax​⋅x,fmin​⋅x,x)
注意这两个式子要同时计算。

代码实现时，可初始化 f m a x = f m i n = 1 f_{max} = f_{min} = 1 fmax​=fmin​=1 ，因为 1 1 1 乘以 n u m s [ 0 ] nums[0] nums[0] 等于 n u m s [ 0 ] nums[0] nums[0] ，这样我们可从下标 0 0 0 开始遍历 n u m s nums nums ，代码写起来更简单。

class Solution {
    public int maxProduct(int[] nums) {
        int ans = Integer.MIN_VALUE; // 注意答案可能是负数
        int fMax = 1;
        int fMin = 1;
        for (int x : nums) {
            int mx = fMax;
            fMax = Math.max(Math.max(fMax * x, fMin * x), x);
            fMin = Math.min(Math.min(mx * x, fMin * x), x);
            ans = Math.max(ans, fMax);
        }
        return ans;
    }
}

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int ans = INT_MIN; // 注意答案可能是负数
        int f_max = 1, f_min = 1;
        for (int x : nums) {
            int mx = f_max;
            f_max = max({f_max * x, f_min * x, x});
            f_min = min({mx * x, f_min * x, x});
            ans = max(ans, f_max);
        }
        return ans;
    }
};

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = -inf  # 注意答案可能是负数
        f_max = f_min = 1
        for x in nums:
            f_max, f_min = max(f_max * x, f_min * x, x), \
                           min(f_max * x, f_min * x, x)
            ans = max(ans, f_max)
        return ans

func maxProduct(nums []int) int {
    ans := math.MinInt // 注意答案可能是负数
    fMax, fMin := 1, 1
    for _, x := range nums {
        fMax, fMin = max(fMax*x, fMin*x, x),
                     min(fMax*x, fMin*x, x)
        ans = max(ans, fMax)
    }
    return ans
}

impl Solution {
    pub fn max_product(nums: Vec<i32>) -> i32 {
        let mut ans = i32::MIN; // 注意答案可能是负数
        let mut f_max = 1;
        let mut f_min = 1;
        for x in nums {
            let mx = f_max;
            f_max = x.max(f_max * x).max(f_min * x);
            f_min = x.min(mx * x).min(f_min * x);
            ans = ans.max(f_max);
        }
        ans
    }
}

var maxProduct = function(nums) {
    let ans = -Infinity; // 注意答案可能是负数
    let fMax = 1, fMin = 1;
    for (const x of nums) {
        const mx = fMax;
        fMax = Math.max(fMax * x, fMin * x, x);
        fMin = Math.min(mx * x, fMin * x, x);
        ans = Math.max(ans, fMax);
    }
    return ans;
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))
#define MIN(a, b) ((b) < (a) ? (b) : (a))

int maxProduct(int* nums, int numsSize) {
    int ans = INT_MIN; // 注意答案可能是负数
    int f_max = 1, f_min = 1;
    for (int i = 0; i < numsSize; i++) {
        int x = nums[i];
        int mx = f_max;
        f_max = MAX(MAX(f_max * x, f_min * x), x);
        f_min = MIN(MIN(mx * x, f_min * x), x);
        ans = MAX(ans, f_max);
    }
    return ans;
}

复杂度分析：

  • 时间复杂度： O ( n ) O(n) O(n) ，其中 n n n 是 n u m s nums nums 的长度。
  • 空间复杂度： O ( 1 ) O(1) O(1) 。
写法3
class Solution {
    public int maxProduct(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int fMax = 1;
        int fMin = 1;
        for (int x : nums) {
            if (x < 0) {
                // 下面与 x 相乘后，最大的正数变成最小的负数，最小的负数变成最大的正数
                // 提前交换，这样可以把 x < 0 和 x >= 0 的情况合并，合并后，计算 max 和 min 可以少一项
                int tmp = fMax;
                fMax = fMin;
                fMin = tmp;
            }
            fMax = Math.max(fMax * x, x);
            fMin = Math.min(fMin * x, x);
            ans = Math.max(ans, fMax);
        }
        return ans;
    }
}

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int ans = INT_MIN;
        int f_max = 1, f_min = 1;
        for (int x : nums) {
            if (x < 0) {
                // 下面与 x 相乘后，最大的正数变成最小的负数，最小的负数变成最大的正数
                // 提前交换，这样可以把 x < 0 和 x >= 0 的情况合并，合并后，计算 max 和 min 可以少一项
                swap(f_max, f_min);
            }
            f_max = max(f_max * x, x);
            f_min = min(f_min * x, x);
            ans = max(ans, f_max);
        }
        return ans;
    }
};

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = -inf
        f_max = f_min = 1
        for x in nums:
            if x < 0:
                # 下面与 x 相乘后，最大的正数变成最小的负数，最小的负数变成最大的正数
                # 提前交换，这样可以把 x < 0 和 x >= 0 的情况合并，合并后，计算 max 和 min 可以少一项
                f_max, f_min = f_min, f_max
            f_max = max(f_max * x, x)
            f_min = min(f_min * x, x)
            ans = max(ans, f_max)
        return ans

func maxProduct(nums []int) int {
    ans := math.MinInt
    fMax, fMin := 1, 1
    for _, x := range nums {
        if x < 0 {
            // 下面与 x 相乘后，最大的正数变成最小的负数，最小的负数变成最大的正数
            // 提前交换，这样可以把 x < 0 和 x >= 0 的情况合并，合并后，计算 max 和 min 可以少一项
            fMax, fMin = fMin, fMax
        }
        fMax = max(fMax*x, x)
        fMin = min(fMin*x, x)
        ans = max(ans, fMax)
    }
    return ans
}

impl Solution {
    pub fn max_product(nums: Vec<i32>) -> i32 {
        let mut ans = i32::MIN;
        let mut f_max = 1;
        let mut f_min = 1;
        for x in nums {
            if x < 0 {
                // 下面与 x 相乘后，最大的正数变成最小的负数，最小的负数变成最大的正数
                // 提前交换，这样可以把 x < 0 和 x >= 0 的情况合并，合并后，计算 max 和 min 可以少一项
                (f_max, f_min) = (f_min, f_max);
            }
            f_max = x.max(f_max * x);
            f_min = x.min(f_min * x);
            ans = ans.max(f_max);
        }
        ans
    }
}

var maxProduct = function(nums) {
    let ans = -Infinity;
    let fMax = 1, fMin = 1;
    for (const x of nums) {
        if (x < 0) {
            // 下面与 x 相乘后，最大的正数变成最小的负数，最小的负数变成最大的正数
            // 提前交换，这样可以把 x < 0 和 x >= 0 的情况合并，合并后，计算 max 和 min 可以少一项
            [fMax, fMin] = [fMin, fMax];
        }
        fMax = Math.max(fMax * x, x);
        fMin = Math.min(fMin * x, x);
        ans = Math.max(ans, fMax);
    }
    return ans;
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))
#define MIN(a, b) ((b) < (a) ? (b) : (a))

int maxProduct(int* nums, int numsSize) {
    int ans = INT_MIN;
    int f_max = 1, f_min = 1;
    for (int i = 0; i < numsSize; i++) {
        int x = nums[i];
        if (x < 0) {
            // 下面与 x 相乘后，最大的正数变成最小的负数，最小的负数变成最大的正数
            // 提前交换，这样可以把 x < 0 和 x >= 0 的情况合并，合并后，计算 MAX 和 MIN 可以少一项
            int tmp = f_max;
            f_max = f_min;
            f_min = tmp;
        }
        f_max = MAX(f_max * x, x);
        f_min = MIN(f_min * x, x);
        ans = MAX(ans, f_max);
    }
    return ans;
}

复杂度分析：

  • 时间复杂度： O ( n ) O(n) O(n) ，其中 n n n 是 n u m s nums nums 的长度。
  • 空间复杂度： O ( 1 ) O(1) O(1) 。

变形题

把子数组改成子序列，要怎么做？

  • [[2708. 一个小组的最大实力值]]

更多相似题目，见动态规划题单中的「§1.3 最大子数组和」。

# leetcode # 动态规划 # 算法
Logo
乐奇 Rokid 开放社区

更多推荐

AI 智能眼镜的柔性神经，开启轻量化人机交互新世代

AI 智能眼镜的核心诉求，是在接近传统眼镜的轻薄体积内，塞进 AI 主控芯片、摄像头、麦克风阵列、骨传导 / 扬声器、光波导显示模组、触控传感器、电池、蓝牙 / Wi-Fi 射频模块等大量器件。随着 AI 眼镜出货量快速上行，鹏鼎、弘信、则成等国内 FPC 厂商纷纷布局 AI 眼镜软板、软硬结合板量产方案，单机 FPC 价值量显著高于 TWS 耳机，带动国内柔性线路板供应链升级，倒逼国内厂商突破超

avatar 乐奇 Rokid 开放社区

听书阁：让你在 AR 眼镜上也可以读小说

戴上眼镜之后我才发现，"翻页"是个需要用手完成的动作。手机上有触屏，滑动、点按、长按选词，一整套肌肉记忆。到了 AR 眼镜上这些全没了：视野只有一小块，手上可能还拎着东西，能稳定输入的只剩嘴和眼镜腿上的几颗按键。把手机阅读器原样搬过来没有意义，得重新想一遍"读一本书"在眼镜上该拆成哪几个动作。听书阁就是这次重想的产物。它跑在 Rokid Craft 上，用 AIUI 的 Ink 写页面，四个页面加

avatar 乐奇 Rokid 开放社区
cover

一期一会 | 什么是抬头显示器（HUD）？

avatar 乐奇 Rokid 开放社区