每日一题——乘积最大子数组

乘积最大子数组问题详解

- 问题描述
- - 示例
  - 约束条件
- 问题分析
- - 难点分析
  - 解题思路
- 代码实现
- - 代码说明
- 测试用例
- - 测试用例 1
  - 测试用例 2
  - 测试用例 3
- 总结

问题描述

给定一个整数数组 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-位整数。

问题分析

本题要求找到一个子数组，使得其乘积最大。由于数组中可能包含负数和零，直接使用暴力解法（枚举所有子数组）的时间复杂度较高，不适用于大规模数据。因此，我们需要寻找更高效的解决方案。

难点分析

负数的影响：负数乘以负数会变成正数，因此最小乘积的子数组可能在某个时刻变成最大乘积的子数组。
零的影响：零会将乘积重置为零，因此需要特别处理零的情况。
动态规划的应用：如何利用已知的子数组乘积信息来推导后续子数组的最大乘积。

解题思路

我们采用动态规划的方法来解决这个问题。具体思路如下：

定义状态：
- dpMax[i]：表示以第 i 个数字结尾的子数组的最大乘积。
- dpMin[i]：表示以第 i 个数字结尾的子数组的最小乘积。
状态转移方程：
- dpMax[i] = max(nums[i], dpMax[i-1] * nums[i], dpMin[i-1] * nums[i])
- dpMin[i] = min(nums[i], dpMax[i-1] * nums[i], dpMin[i-1] * nums[i])
由于负数的存在，最小乘积的子数组可能在某个时刻变成最大乘积的子数组，因此需要同时维护最大值和最小值。
初始化：
- dpMax[0] = nums[0]
- dpMin[0] = nums[0]
结果：
- 遍历整个数组，更新全局最大乘积 result。

代码实现

以下是完整的C语言代码实现：

#include <stdio.h>
#include <stdlib.h>// 返回三个数中的最大值
int threeMax(int a, int b, int c) {return (a > b ? (a > c ? a : c) : (b > c ? b : c));
}// 返回三个数中的最小值
int threeMin(int a, int b, int c) {return (a < b ? (a < c ? a : c) : (b < c ? b : c));
}// 求解乘积最大子数组
int maxProduct(int* nums, int numsSize) {if (numsSize == 0) {return 0;  // 空数组的情况}// 动态分配内存int* dpMax = (int*)malloc(sizeof(int) * numsSize);int* dpMin = (int*)malloc(sizeof(int) * numsSize);// 初始化第一个元素dpMax[0] = nums[0];dpMin[0] = nums[0];int result = nums[0];  // 用于存储全局最大乘积// 遍历数组，更新 dpMax 和 dpMinfor (int i = 1; i < numsSize; i++) {dpMax[i] = threeMax(nums[i], dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]);dpMin[i] = threeMin(nums[i], dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]);// 更新全局最大乘积result = (result > dpMax[i]) ? result : dpMax[i];}// 释放动态分配的内存free(dpMax);free(dpMin);return result;
}// 测试函数
int main() {int nums1[] = {2, 3, -2, 4};int nums2[] = {-2, 0, -1};int nums3[] = {-2, 3, -4};printf("Test Case 1: %d\n", maxProduct(nums1, sizeof(nums1) / sizeof(nums1[0])));printf("Test Case 2: %d\n", maxProduct(nums2, sizeof(nums2) / sizeof(nums2[0])));printf("Test Case 3: %d\n", maxProduct(nums3, sizeof(nums3) / sizeof(nums3[0])));return 0;
}