本文共 2871 字，大约阅读时间需要 9 分钟。

链接：

大意：

给定一个整型数组nums，数组中元素可正可负可为0.要求找出一个连续子数组，使得该子数组是所有子数组中各元素最大，返回最大的乘积。例子：

思路：

一开始感觉应该用动态规划来做，但是递推方程式始终没想出来。于是只能老老实实地做了...

首先使用一个列表 zeros记录数组中所有0所在的位置，在遍历数组时，主要做两个事：

1. 记录当前的乘积max（从nums[0]到nums[i]）
2. 若当前元素为0，则将当前位置add到zeros

第一次遍历完之后，首先判断max是否大于0.

1. 若max大于0，则可以直接返回max了
2. 若max<=0并且zeros.size()==0，也就是数组中没有0，但是肯定有负数（不然max怎么可能小于0）。那么对于整个数组，找到第一个正数到一个负数之间（包含首尾）的乘积negVOne以及最后一个负数到最后一个正数之间（包含首尾）的乘积negVLast。对于整个区间的成绩v，返回 Math.max(v / negVOne, v / negVLast)

若上面的情况都不满足，也就是max<0并且数组中含有元素0.则需要针对元素0的位置，对数组进行分段，依次求得每一段的最大连续子数组乘积，再比较返回最大的乘。（在代码中即为helper函数）

代码：

class Solution {    public int maxProduct(int[] nums) {        if (nums.length == 0)            return 0;        int max = 1, i = 0;        ArrayList
   
     zeros = new ArrayList<>(); // 存储所有0的位置        for (int num : nums) {            max *= num;            if (num == 0)                zeros.add(i);            i++;        }        if (max > 0)            return max;        else if (zeros.size() == 0)            return helper(nums, 0, nums.length - 1);        max = 0;        int s = 0;        // 通过元素0 将原数组分成n段        for (int e : zeros) {            max = Math.max(helper(nums, s, e - 1), max);            s = e + 1;        }        max = Math.max(helper(nums, s, nums.length - 1), max);        return max;    }    public int helper(int[] nums, int s, int e) {        if (s == e)            return nums[s];        if (s > e)            return Integer.MIN_VALUE;        int negOne = -1, negLast = -1; // 记录当前段中第一个和最后一个负数的位置        int negVOne = 1, negVLast = 1; // 记录第一个负数左边的乘积（包括负数） 和 最后一个负数右边的乘积（包括负数）        int v = 1;        while (s <= e) {            if (negOne == -1) { // 还未找到第一个负数                negVOne *= nums[s];            } else if (negLast != -1) // 已找到除第一个负数之外的另一个负数                negVLast *= nums[s];            if (nums[s] < 0) {                if (negOne == -1) {                    negOne = negLast = s;                  } else {                    negLast = s;                }                negVLast = nums[s];            }            v *= nums[s]; // v只管乘            s++;        }        if (v > 0)            return v;        return Math.max(v / negVOne, v / negVLast);    }}
   

结果：

结论:

仍然感觉得用动态规划好些，虽然这个解法 时间复杂度为 O(n)，空间复杂度为O(n)。 但是用动态规划应该会更好看。

最佳：（动态规划）

class Solution {    // 若最终的结果小于0 则表明有奇数个负数 需要干掉一段负数（可能附带正数） 被干掉的肯定是第一段或者最后一段    public int maxProduct(int[] nums) {        if(nums == null || nums.length ==0) return 0;        int max = nums[0];        int currMax = 1;        for(int i =0; i< nums.length ;i++){            currMax *= nums[i];            if(currMax > max) max=currMax;            if(currMax ==0) currMax =1; // 遇到0则重新开始        }                currMax = 1;        for(int i =nums.length-1; i >=0 ;i--){            currMax *= nums[i];            if(currMax > max) max=currMax;                if(currMax ==0) currMax =1; // 遇到0则重新开始        }                return max;    }}

转载地址：http://exesi.baihongyu.com/