乘积最大子数组

题目要求

编写一个函数，该函数接收一个整数数组 nums 作为参数。你需要在这个数组中找到一个非空连续子数组，使得这个子数组中所有元素的乘积最大。返回这个最大乘积的值。结果必须是一个 32 位整数，即它必须在 [-2^31, 2^31 - 1] 的范围内。

解题思路

要解决这个问题，我们可以采用动态规划的方法。动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。对于这个问题，我们可以维护两个变量，分别记录到当前位置为止的最大乘积和最小乘积（因为一个负数乘以最小乘积可能会变成最大乘积）。

初始化两个变量 max_product 和 min_product，它们都等于数组的第一个元素，这代表了到目前为止的最大和最小乘积。同时，初始化最终的最大乘积 max_result 为数组的第一个元素。
从数组的第二个元素开始遍历，对于每个元素 nums[i]：
- 计算包含当前元素的最大乘积 current_max，它是以下三者中的最大值：nums[i]、nums[i] * max_product、nums[i] * min_product。
- 计算包含当前元素的最小乘积 current_min，它是以下三者中的最小值：nums[i]、nums[i] * max_product、nums[i] * min_product。
- 更新 max_product 和 min_product 的值为 current_max 和 current_min。
- 更新 max_result 为 max_product 和 max_result 中的最大值。
遍历完成后，max_result 将包含数组中乘积最大的非空连续子数组的乘积。

注意：由于乘积可能会因为负数的存在而从最大变成最小，反之亦然，所以我们需要同时跟踪最大值和最小值。

这个问题的关键在于理解负数和零如何影响乘积，并且如何利用动态规划来跟踪和更新这些乘积。

Golang 版本

package main

import (
	"fmt"
	"math"
)

func maxProduct(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	maxProduct, minProduct, maxResult := nums[0], nums[0], nums[0]

	for i := 1; i < len(nums); i++ {
		if nums[i] < 0 {
			maxProduct, minProduct = minProduct, maxProduct
		}
		maxProduct = max(nums[i], maxProduct*nums[i])
		minProduct = min(nums[i], minProduct*nums[i])
		maxResult = max(maxResult, maxProduct)
	}

	return maxResult
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func main() {
	nums := []int{2, 3, -2, 4}
	fmt.Println("Maximum product of a subarray is:", maxProduct(nums))
}

这段代码定义了一个 maxProduct 函数，它接收一个整数数组 nums 并返回乘积最大的连续子数组的乘积。在 main 函数中，我们定义了一个测试用例，并打印出调用 maxProduct 函数的结果。

C++版本

#include <iostream>
#include <vector>
#include <algorithm>

int maxProduct(const std::vector<int>& nums) {
    if (nums.empty()) return 0;

    int maxProduct = nums[0];
    int minProduct = nums[0];
    int maxResult = nums[0];

    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] < 0) {
            std::swap(maxProduct, minProduct);
        }
        maxProduct = std::max(nums[i], maxProduct * nums[i]);
        minProduct = std::min(nums[i], minProduct * nums[i]);
        maxResult = std::max(maxResult, maxProduct);
    }

    return maxResult;
}

int main() {
    std::vector<int> nums = {2, 3, -2, 4};
    std::cout << "Maximum product of a subarray is: " << maxProduct(nums) << std::endl;
    return 0;
}

这段代码定义了一个 maxProduct 函数，它接收一个整数类型的 std::vector 作为参数，并返回乘积最大的连续子数组的乘积。在 main 函数中，我们定义了一个测试用例，并打印出调用 maxProduct 函数的结果。这里使用了 <algorithm> 头文件中的 std::max 和 std::min 函数来简化代码。

Python 版本

def max_product(nums):
    if not nums:
        return 0

    max_product = min_product = max_result = nums[0]

    for i in range(1, len(nums)):
        if nums[i] < 0:
            max_product, min_product = min_product, max_product
        max_product = max(nums[i], max_product * nums[i])
        min_product = min(nums[i], min_product * nums[i])
        max_result = max(max_result, max_product)

    return max_result

# 测试用例
nums = [2, 3, -2, 4]
print("Maximum product of a subarray is:", max_product(nums))

这段代码定义了一个 max_product 函数，它接收一个整数列表 nums 作为参数，并返回乘积最大的连续子数组的乘积。在测试用例中，我们定义了一个列表，并打印出调用 max_product 函数的结果。这里使用了 Python 内置的 max 和 min 函数来简化代码。

Java 版本

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Input array is null or empty");
        }

        int maxProduct = nums[0];
        int minProduct = nums[0];
        int maxResult = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = maxProduct;
                maxProduct = minProduct;
                minProduct = temp;
            }
            maxProduct = Math.max(nums[i], maxProduct * nums[i]);
            minProduct = Math.min(nums[i], minProduct * nums[i]);
            maxResult = Math.max(maxResult, maxProduct);
        }

        return maxResult;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 3, -2, 4};
        System.out.println("Maximum product of a subarray is: " + solution.maxProduct(nums));
    }
}

这段代码定义了一个名为 Solution 的类，其中包含一个 maxProduct 方法，该方法接收一个整数数组 nums 作为参数，并返回乘积最大的连续子数组的乘积。在 main 方法中，我们创建了一个 Solution 对象，并定义了一个测试用例，然后打印出调用 maxProduct 方法的结果。这里使用了 Java 的 Math.max 和 Math.min 方法来简化代码。

Rust 版本

fn max_product(nums: Vec<i32>) -> i32 {
    use std::cmp::{max, min};

    let (mut max_product, mut min_product, mut max_result) = (nums[0], nums[0], nums[0]);

    for &num in nums.iter().skip(1) {
        let (temp_max, temp_min) = (max_product, min_product);
        max_product = max(num, max(temp_max * num, temp_min * num));
        min_product = min(num, min(temp_max * num, temp_min * num));
        max_result = max(max_result, max_product);
    }

    max_result
}

fn main() {
    let nums = vec![2, 3, -2, 4];
    println!("Maximum product of a subarray is: {}", max_product(nums));
}

这段代码定义了一个 max_product 函数，它接收一个 Vec<i32> 类型的整数向量 nums 作为参数，并返回乘积最大的连续子数组的乘积。在 main 函数中，我们定义了一个测试用例，并打印出调用 max_product 函数的结果。这里使用了 Rust 的 std::cmp::{max, min} 来简化代码。

总结

上述代码段展示了如何在不同编程语言中实现寻找给定整数数组中乘积最大的连续子数组的问题。尽管每种语言的语法不同，但它们共享相同的核心算法逻辑：

初始化三个变量，分别用于存储当前的最大乘积、最小乘积（考虑到负数的影响）以及迄今为止的最大乘积结果。
遍历数组，对于每个元素：
- 如果当前元素是负数，则交换最大乘积和最小乘积的值，因为乘以负数会使得最大变最小，最小变最大。
- 更新当前最大乘积和最小乘积的值，这是通过将当前元素与当前元素与之前最大乘积和最小乘积的乘积进行比较得出的。
- 更新迄今为止的最大乘积结果。
遍历完成后，返回迄今为止的最大乘积结果。

这个问题的关键点在于理解如何处理负数对乘积的影响，以及如何在遍历数组的过程中更新和维护最大乘积和最小乘积。动态规划的思想在这里得到了应用，即每一步都基于前一步的结果进行决策和更新。

在实现上，每种语言都使用了其标准库中的最大值和最小值函数（如 max 和 min），以及对数组或向量的迭代方法。尽管实现细节各有不同，但核心算法和逻辑是一致的。

hot-100