关于java:LeetCode152乘积最大子数组

43次阅读

共计 957 个字符，预计需要花费 3 分钟才能阅读完成。

题目形容：给你一个整数数组 nums，请你找出数组中乘积最大的间断子数组（该子数组中至多蕴含一个数字），并返回该子数组所对应的乘积。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：穷举法

首先，如果数组 nums 只有一个元素，间接返回这个数。

否则，通过穷举出所有可能的间断子数组的乘积，而后获取较大者，应用 result 记录最大值，初始化为数组 nums 的第一个元素值，具体过如下：

从第一个元素开始遍历，作为间断子数组的第一个元素；

而后内层循环是作为间断子数组的最初一个数组，过程中须要判断以后的间断子数组的乘积是否大于 result，如果是则更新 result 的值。

最初，返回 result 即为最大的乘积。

public class LeetCode_152 {
    /**
     * 穷举法
     *
     * @param nums 原数组
     * @return 返回数组中乘积最大的间断子数组的乘积
     */
    public static int maxProduct(int[] nums) {
        // 如果数组 nums 只有一个元素，间接返回这个数
        if (nums.length == 1) {return nums[0];
        }
        // result 记录当期的最大值
        int result = nums[0];
        // 从数组的 nums 的第一个元素开始遍历
        for (int i = 0; i < nums.length; i++) {int cur = nums[i];
            // result 取较大值
            result = Math.max(result, cur);
            // 以后元素直到和最初一个元素的累乘
            for (int j = i + 1; j < nums.length; j++) {cur = cur * nums[j];
                // result 取最大值
                result = Math.max(result, cur);
            }
        }

        return result;
    }

    public static void main(String[] args) {int[] nums = new int[]{2, 3, -2, 4};
        // 测试用例，冀望输入：6
        System.out.println(maxProduct(nums));
    }
}