Find the contiguous subarray within an array (containing at least one number) which has the largest product. For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.
刚看完覃超的直播。他说先不要用野路子dp,先老实开辟一个维度。 这题为什么要开辟一个新维度呢,因为这题要维护上一个最优值是max positive和min negtive两种情况。
public class Solution { //dp[index][正负] //dp[i][0] = dp[i-1][0] * nums[i] (nums[i]>=0) or dp[i-1][1] * nums[i](nums[i]<0) //dp[i][1] = dp[i-1][1] * nums[i] (nums[i]>=0) or dp[i-1][0] * nums[i](nums[i]<0) public int maxProduct(int[] nums) { if (nums.length==0) return 0; int dp[][] = new int[nums.length][2]; dp[0][0] = nums[0]; dp[0][1] = nums[0]; int res = nums[0] ; for (int i = 1; i < nums.length; i++) { if (nums[i] >= 0) { dp[i][0] = dp[i - 1][0] * nums[i]; dp[i][1] = dp[i - 1][1] * nums[i]; } else { dp[i][0] = dp[i - 1][1] * nums[i]; dp[i][1] = dp[i - 1][0] * nums[i]; } dp[i][0] = Math.max(dp[i][0] , nums[i]); dp[i][1] = Math.min(dp[i][1] , nums[i]); res = Math.max(res,dp[i][0]); } return res; }}复制代码
他这种写法,理解起来并不简单。。同样涉及到local跟global的那种原理。至少我现在很晕,可能因为很困了。12点多了还在公司,日。这题还可以状态压缩。
对于这种dp,还是要找时间跟code ganker那种local global的「」(其实我觉得他那种也不算野路子,也是一种套路)都好好理一遍。
12/04/2017更新
刚才又看了一遍这个题,重新定义了一遍状态:
nums[i]>=0 : dpPos[i] = dpPos[i-1] * nums[i] 这里dpPos只存放positive max的值 dpNeg[i] = dpNeg[i-1] * nums[i] 这里dpMin只存放negative min的值 nums[i]<0 : dpNeg[i] = dpPos[i-1] * nums[i] 这里dpPos只存放positive max的值 dpPos[i] = dpNeg[i-1] * nums[i] 这里dpMin只存放negative min的值
这个方程对应的解法,九章上有:http://www.jiuzhang.com/solutions/maximum-product-subarray/
用野路子的空间轮换做了一遍,没有分开两个数组,而是只用了max min两个变量存储:
public int maxProduct(int[] nums) { if (nums.length == 0) return 0; int res = nums[0]; int maxPos = nums[0]; int minNeg = nums[0]; for (int i = 1; i < nums.length; i++) { if (nums[i] >= 0) { maxPos = maxPos * nums[i]; minNeg = minNeg * nums[i]; } else { int minNegCopy = minNeg; minNeg = maxPos * nums[i]; maxPos = minNegCopy * nums[i]; } maxPos = Math.max(maxPos, nums[i]); minNeg = Math.min(minNeg, nums[i]); res = Math.max(maxPos, res); } return res; }复制代码
这里注意那个Math.max在比较maxPos和minNeg的时候也要跟当前数字对比,我一开始不懂,后来了解到因为如果给这两个变量都初始化nums[0]的话,这样做就有道理了。还有,由于没有采用数组,这里需要创建一个minNegCopy。
code ganker的 local global解法:
public int maxProduct(int[] A) { if(A==null || A.length==0) return 0; if(A.length == 1) return A[0]; int max_local = A[0]; int min_local = A[0]; int global = A[0]; for(int i=1;i
他这边都没有判断nums[i]正负了,而是把三个数一起比较,很聪明。