乘积最大子数组 - LeetCode 热题 88

本文主要是介绍乘积最大子数组 - LeetCode 热题 88，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大家好！我是曾续缘😆

今天是《LeetCode 热题 100》系列

发车第 88 天

动态规划第 8 题

❤️点赞 👍 收藏 ⭐再看，养成习惯

乘积最大子数组
给你一个整数数组 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⁴
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都保证是一个 32-位 整数
难度：💖💖

解题方法

在解决这个问题时，我们的目标是找到一个整数数组中的最大乘积非空连续子数组。这里有一个重要的观察点：一个负数乘以另一个负数会得到一个正数，而一个负数乘以一个正数或者一个正数乘以另一个正数，结果都是负数或者正数。因此，当我们寻找最大乘积时，我们应该同时跟踪到当前位置为止的最大乘积和最小乘积，因为最小的负数乘积可能会在下一刻变成最大的正数乘积。

定义状态：我们定义一个二维数组 f，其中 f[i][0] 表示以 nums[i] 结尾的子数组的最大乘积，f[i][1] 表示以 nums[i] 结尾的子数组的最小乘积。可以认为f[i][1] 是负数，如果非负，也不影响 f[i][0] 。下面使用 f[i][0] 表示正， f[i][0]表示负。
初始化状态：数组的第一位数字，其最大乘积和最小乘积都是它本身，即 f[0][0] = nums[0]，f[0][1] = nums[0]。
状态转移方程：对于数组的每一位数字，我们需要考虑两种情况：
- 如果当前数字 nums[i] 是正数，那么最大乘积可能是由之前的正乘以当前的正数得到的，也可能是当前数字本身；最小乘积可能是由之前的负乘以当前的正数得到的，也可能是当前数字本身。
- 如果当前数字 nums[i] 是负数，那么最大乘积可能是由之前的负乘以当前的负数得到的，也可能是当前数字本身；最小乘积可能是由之前的正乘以当前的负数得到的，也可能是当前数字本身。
更新状态：根据上述状态转移方程，我们可以更新 f[i][0] 和 f[i][1] 的值。
找出最终答案：在整个数组遍历完成后，我们需要找出所有的 f[i][0] 中的最大值，这个值就是最大乘积的子数组乘积。

Code

class Solution {public int maxProduct(int[] nums) {int n = nums.length;int[][] f = new int[n][2];f[0][0] = nums[0];f[0][1] = nums[0];for(int i = 1; i < n; i++){if(nums[i] >= 0){f[i][0] = Math.max(f[i - 1][0] * nums[i], nums[i]);f[i][1] = Math.min(f[i - 1][1] * nums[i], nums[i]);}else{f[i][0] = Math.max(f[i - 1][1] * nums[i], nums[i]);f[i][1] = Math.min(f[i - 1][0] * nums[i], nums[i]);}}int ans = f[0][0];for(int i = 1; i < n; i++){ans = Math.max(ans, f[i][0]);}return ans;}
}