本文共 3336 字，大约阅读时间需要 11 分钟。
[DP解题] 乘积最大子序列
原题链接：
[问题]
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]Output: 6Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]Output: 0Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
题目的意思是给定一个整形数组nums，要求在数组中找到连续的子序列使得子序列的乘积最大（子序列至少包含一个整数）
例如：给定数组 [2,3,-2,4]，最大连续子序列乘积为6。因为最大的连续子序列 [2,3]，其最大乘积为6。
[算法分析]
这道题最直接的方法就是用DP来做，而且要用两个dp变量，其中：
dpMax:代表nums数组中下标从[0...i]时的最大乘积 dpMin:代表nums数组中下标从[0...i]时的最小乘积
为什么呢？
初始时，当i=0时，即数组中的第一个元素：
dpMax=dpMin=answer=nums[0] （可能为0，正值，负值）
当i=1时：即数组中的第二个元素，这时要考虑几种情况，
乘积为0时——有可能数组中的第一个元素为零，也可能数组中的第二个元素为零；无论哪一种结果，其乘积为零；
乘积为正值时——数组中的第一个元素和第二个元素均为正值或者均为负值时，则乘积为正值；
乘积为负值时——数组中的第一个元素为负值，或者第二个元素为负值，则乘积为负值；
综合起来，要取 Math.max(nums[i]*dpMax, nums[i]*dpMin)
然后在用这个乘积的值与nums[i]做比较得到当前的最大值
currentMax = Math.max(nums[i], Math.max(nums[i] * dpMax, nums[i] * dpMin));
举例来分析，先看第一个数组，仅包含两个数组元素
例如数组 [-2,-7]：
当i=0时：dpMax = dpMin = answer = nums[0] = -2
当i=1时：dpMax是多少？要从 （-2）*（-7）=14，前面的dpMax （-2）和 nums[1] 中经过比较选出最大值，显然是 14。
dpMin是多少？显然是 -7。为什么？Math.min(nums[i], Math.min(nums[i] * dpMax, nums[i] * dpMin))
如果把数组变为 [-2,7]：
当i=0时：dpMax = dpMin = answer = nums[0] = -2
当i=1时：dpMax是多少？要从 （-2）* 7= -14，前面的dpMax （-2）和 nums[1] 中经过比较选出最大值，显然是7。
dpMin是多少？-14。为什么？Math.min(nums[i], Math.min(nums[i] * dpMax, nums[i] * dpMin));
再看第二个数组，仅包含三个数组元素
例如数组 [-2,-7,-3]：
当i=0时：dpMax = dpMin = answer = nums[0] = -2
当i=1时：dpMax是多少？要从 （-2）*（-7）=14，前面的dpMax （-2）和 nums[1] 中经过比较选出最大值，显然是 14。
而此时dpMin是多少？显然此时dpMin的值为 -7.
当i=2时：dpMax是多少？这时num[2]为负值，当i=1时，dpMax=14，那么dpMax*nums[2] = 14*(-3) = -42 < nums[2]的值。
显然 dpMax*nums[2] 不是最大值。那么 nums[2] 是最大值吗？显然也不是。
那么最大值是多少？ 用i=1时的dpMin*nums[2]看看，即 （-7）*（-3）=21. 这个最大值dpMax = 21.
dpMax = Math.max(nums[i], Math.max(nums[i] * dpMax, nums[i] * dpMin));
那么最小值是多少？-42. 用前面的最大值与当前元素的乘积得到。
dpMin = Math.min(nums[i], Math.min(nums[i] * dpMax, nums[i] * dpMin));
从而可以推导出：
对于nums数组中的第i个元素为止：
dpMax = Math.max(nums[i], Math.max(nums[i] * dpMax, nums[i] * dpMin));
dpMin = Math.min(nums[i], Math.min(nums[i] * dpMax, nums[i] * dpMin));
所以，我们不仅仅要找dpMax，还要找dpMin。
看看其中有什么规律？
[算法设计]
package com.bean.algorithmexec;public class MaximumProductSubarray { public static int maxProduct(int[] nums) { /* * dpMax:代表nums数组中下标从[0...i]时的最大乘积 * dpMin:代表nums数组中下标从[0...i]时的最小乘积 * */ int dpMax = nums[0]; //初始时将nums[0]赋给dpMax int dpMin = nums[0]; //初始时将nums[0]赋给dpMin int answer = nums[0];//代表求得的结果，初始时将nums[0]赋给answer //从下标i=1开始，遍历到nums数组的最后一个元素为止 for (int i = 1; i < nums.length; i++) { /* * 如果下标为i的前一个元素，即i-1为0时，则前面元素的乘积必定为0; * 那么当前元素nums[i] * */ if (nums[i - 1] == 0) { dpMax = nums[i]; dpMin = nums[i]; } else { int currentMax = Math.max(nums[i], Math.max(nums[i] * dpMax, nums[i] * dpMin)); int currentMin = Math.min(nums[i], Math.min(nums[i] * dpMax, nums[i] * dpMin)); dpMax = currentMax; dpMin = currentMin; } answer = Math.max(dpMax, answer); //answer = Math.min(dpMin, answer); } return answer; } public static void main(String[] args) { // TODO Auto-generated method stub //int[] demo=new int[] {2,3,-2,4}; //int[] demo=new int[] {-1,4,-7,0,8,2,3}; int[] demo=new int[] {-2,-7,-3}; int result=0; result = maxProduct(demo); System.out.println("RESULT = "+result); }} 执行结果
RESULT = 21
转载地址：http://ddtdi.baihongyu.com/