LeetCode题解：乘积最大子数组

题目描述

给你一个整数数组nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个32位整数。
子数组是数组的连续子序列。

示例

• 示例1
  输入：nums = [2,3,-2,4]
  输出：6
  解释：子数组 [2,3] 有最大乘积 6。
• 示例2
  输入：nums = [-2,0,-1]
  输出：0
  解释：结果不能为 2, 因为 [-2,-1] 不是子数组。

思路方法

看到这道题，我相信很多的小伙伴都想到了前面的“最大子数组”的问题，而且肯定第一反应是使用“最大子数组”的解法去解决这道题。没错，小编刚开始也是这么想的，但是，这就错了！
因为这道题不满足“最大子数组”的最优子结构。
具体地讲，如果a={5,6,−3,4,−3}，那么此时 fmax对应的序列是 {5,30,−3,4,−3}，按照前面的算法我们可以得到答案为 30，即前两个数的乘积，而实际上答案应该是全体数字的乘积。我们来想一想问题出在哪里呢？问题出在最后一个−3 所对应的 fmax的值既不是 −3，也不是4×−3，而是5×30×(−3)×4×(−3)。所以我们得到了一个结论：当前位置的最优解未必是由前一个位置的最优解转移得到的。
我们可以从正负性进行讨论
考虑当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，即尽可能小。如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。于是这里我们可以再维护一个 fmin(i)，它表示以第 i 个元素结尾的乘积最小子数组的乘积，那么我们可以得到这样的动态规划转移方程：

image.png
它代表第 i 个元素结尾的乘积最大子数组的乘积 fmax(i)，可以考虑把ai加入第 i−1 个元素结尾的乘积最大或最小的子数组的乘积中，二者加上ai，三者取大，就是第i个元素结尾的乘积最大子数组的乘积。第 i 个元素结尾的乘积最小子数组的乘积 fmin(i) 同理。

class Solution {
    public int maxProduct(int[] nums) {
        int length = nums.length;
        int[] maxF = new int[length];
        int[] minF = new int[length];
        System.arraycopy(nums,0,maxF,0,length);
        System.arraycopy(nums,0,minF,0,length);
        for(int i=1;i<length;i++){
            maxF[i] = Math.max(nums[i]*maxF[i-1],Math.max(nums[i],nums[i]*minF[i-1]));
            minF[i] = Math.min(nums[i]*minF[i-1],Math.min(nums[i],nums[i]*maxF[i-1])); 
        }
        int result = maxF[0];
        for(int i=1;i<length;i++){
            result = Math.max(maxF[i],result);
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

优化空间

class Solution {
    public int maxProduct(int[] nums) {
        int maxF=nums[0],minF=nums[0],result=nums[0];
        int length = nums.length;
        for(int i=1;i<length;i++){
            int max = maxF,min = minF;
            maxF = Math.max(max*nums[i],Math.max(nums[i],min*nums[i]));
            minF = Math.min(min*nums[i],Math.min(nums[i],max*nums[i]));
            result = Math.max(result,maxF);
        }
        return result;
    }
}