leetcode hot100【LeetCode 152. 乘积最大子数组】java实现

LeetCode 152. 乘积最大子数组

题目描述

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

示例 1:

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

示例 2:

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

Java 实现代码

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) return 0;

        int maxProd = nums[0];
        int minProd = nums[0];
        int result = maxProd;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                // 负数会导致最大值和最小值交换
                int temp = maxProd;
                maxProd = minProd;
                minProd = temp;
            }

            maxProd = Math.max(nums[i], maxProd * nums[i]);
            minProd = Math.min(nums[i], minProd * nums[i]);

            result = Math.max(result, maxProd);
        }

        return result;
    }
}

解题思路

1. 动态规划: 使用两个变量 maxProd 和 minProd 来分别记录到当前位置的最大乘积和最小乘积。因为乘以负数可能会使最小乘积变成最大乘积。
2. 迭代: 遍历数组，对于每个元素，更新当前的最大和最小乘积。然后根据当前元素的符号决定如何更新它们。
3. 结果: 在遍历过程中，维护一个全局最大乘积。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需遍历数组一次。
• 空间复杂度：O(1)，只使用了常数个额外的空间来存储变量。

注：题目来源leetcode网站

原文地址：https://blog.csdn.net/qq_14815605/article/details/143427779

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！