给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
子序列问题优先考虑动态规划！拿到题一上来的思路是：因为数组中都是整数，所以在保证成绩为正的情况下(负数个数为偶数)，包含最多的负数。
若数组中负数个数为偶数，则答案为数组全部的乘积。若负数个数为偶数，则答案为第一个负数后的所有数相乘，或最后一个负数前所有数的乘积。
但是，由于有0的存在，导致这个思路十分复杂。每出现一个零，就要将数组分段。分段后，每段都要考虑偶数个数等等。所以最终放弃了这个想法。
对于动态规划来说，选好dp的含义就成功了一大半！在本题中，dp为以nums[i]结尾的子串乘积最大值，为了应对负数，同理建立dp记录以nums[i]结尾的最小子串乘积。
这样dp[i-1]与dp[i]才好建立联系。与此同时，需要引入一个变量来保存最终结果。
1 package Leetcode; 2 3 public class maxProduct { 4 public int maxProduct(int[] nums) { 5 if(nums.length==0){return 0;} 6 if(nums.length==1){return nums[0];} 7 int max = nums[0]; 8 int min = nums[0]; 9 int res = nums[0]; 10 //相当于维护两个dp，含义为以第i位结尾的子序列乘积最大值和最小值，引入第三方变量res记录res。优化dp的空间。 11 for (int i = 1; i <nums.length ; i++) { 12 if(nums[i]>=0){ 13 max = Math.max(nums[i],max*nums[i]); 14 min = Math.min(nums[i],min*nums[i]); 15 res = Math.max(res,max); 16 }else{ 17 int temp = max; 18 max = Math.max(min*nums[i],nums[i]); 19 min =Math.min(nums[i],nums[i]*temp); 20 res = Math.max(max,res); 21 } 22 } 23 return res; 24 } 25 26 public static void main(String[] args) { 27 maxProduct m = new maxProduct(); 28 m.maxProduct(new int[]{2,3,-2,4}); 29 } 30 }
细节：在第十九行代码中，需要用到的max值在第十八行已经并更，要提前引入temp存储
原文：https://www.cnblogs.com/zhangbochao/p/12372144.html