乘积最大子数组 - 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 * 104
• -10 <= nums[i] <= 10
• nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

难度：💖💖

解题方法

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

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