题目：

乘积最大子序列

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

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

思路：

 

先定义一个二维dp数组dp[i][0]   dp[i][1]，其中一个用来保存到当前位置存在的最大值，另一个保存到当前位置的最小值，因为有负数的存在，所以   最大值和最小值会在遇到负数的时候互换，因此才会保存两个值一个最大值一个最小值。因为求的是连续的子序列(这样的话就不会有跳跃的子集，子集都是连续的)，所以每一次dp只需要比较上一次dp的最大值与当前位置的乘积的值  和  当前位置的值，它俩谁大就取用谁。最后只需要取出dp数组中最大的数即可。

 

代码：

public static int maxProduct(int[] nums) { //dp[i][0]表示到nums[i-1]位置的最大值 //dp[i][1]表示到nums[i-1]位置的最小值 int n = nums.length; //增加边界条件 if (n == 0) return 0; if (n == 1) return nums[0]; //定义一个二维dp数组，用来保存最大最小值，其中第一个是初始的值 不作为判断。 int[][] dp = new int[n + 1][2]; dp[0][0] = 1; dp[0][1] = 1; for (int i = 1; i <= n; i++) { if (nums[i - 1] < 0) { dp[i][0] = Math.max(nums[i - 1], dp[i - 1][1] * nums[i - 1]); dp[i][1] = Math.min(nums[i - 1], dp[i - 1][0] * nums[i - 1]); } else { dp[i][0] = Math.max(nums[i - 1], dp[i - 1][0] * nums[i - 1]); dp[i][1] = Math.min(nums[i - 1], dp[i - 1][1] * nums[i - 1]); } } int maxVal = Integer.MIN_VALUE; //这是所有的情况都被存在这个dp数组中，只要遍历找到最大的就可以。 for (int i = 1; i <= n; i++) { maxVal = Math.max(maxVal, dp[i][0]); } return maxVal; }

 

//还有一种解法，不使用dp数组，思路是一样的，记录最大最小两个数值，每次先比较 乘积和当前位置的大小，取最大最小值，每次遇到负数翻转最大最小值，最后取结果就可以。 public static int maxProduct(int[] nums) { if (nums.length == 1) return nums[0]; int result = Integer.MIN_VALUE; max = 1; min = 1; for (int i = 0; i < nums.length; i++) { //小于0，交换最大最小值。 if (nums[i] < 0) { int tmp = max; max = min; min = tmp; } //比较乘积和当前位置的值的大小 max = Math.max(max * nums[i], nums[i]); min = Math.min(min * nums[i], nums[i]); result = Math.max(result, max); } return result; }

结果：