Leetcode – Maximum Product Subarray

为了今天的相遇付出太多的艰辛未来的路依然崎岖何时何地不言放弃为了现在的相聚一路走来不容易希望彼此倍加珍惜守护爱情这片天地我想和你在一起让你住进我心里不管前方几多风雨再苦再累没关系我想和你在一起为了明天而努力风雨同舟不离不弃相伴一生到老去My
Love 你给我翅膀我陪你翱翔My Lover 你给我力量我伴你成长

图片 1Paste_Image.png

版权作品,未经《短文学》书面授权,严禁转载,违者将被追究法律责任。

My code:

public class Solution { public int maxProduct(int[] nums) { if (nums == null || nums.length == 0) return 0; else if (nums.length == 1) return nums[0]; int max = nums[0]; int currMax = nums[0]; int currMin = nums[0]; for (int i = 1; i < nums.length; i++) { int temp = currMax; currMax = Math.max(Math.max(currMax * nums[i], currMin * nums[i]), nums[i]); currMin = Math.min(Math.min(temp * nums[i], currMin * nums[i]), nums[i]); max = Math.max(max, currMax); } return max; }}

My test result:

图片 2

这道题目还是没能自己想出来,看了提示。

来仔细分析下。这道题目和前面一题求和,有什么区别。求和的话,当你出现了和为负数的情况后,这个情况就结束了。就可以重新开始开头遍历了。比如,
-5, 2,1,1,1,1当遍历到,-5, 2时,和为-3 < 0, 那么后面的和一定是 >=
该和,只要后面存在正数。于是,这段值,就不需要再考虑了。直接可以从下一个正数开始考虑了。但是乘积不同。-5,
2, 3, -4遍历到 -5,
2时,此时是负数,但不代表这段值就没用了。如果后面还存在一个负数,那么,这一段,积就是最大的,所以不能简单地舍弃。于是我就在想,怎么保存这些一开始是负数最后却可能变成最大正数的情况。解决不了,于是看了提示。设置两个变量,
currMax, currMin主要在于这个currMin,
可以用来保存负数,然后下次这个负数乘以负数,说不定就成了 currMax.
然后可以保存住这些情况。所以可以这么理解。这段array,一定存在一个最大的正数,以及一个绝对值最大的负数。然后一个一定是整段array的乘积。还有一个一定是,在出现了一个负数之后的那段array的乘积。这两个乘积一定一个是最大正数,一个是绝对值最大的负数。

然后刚刚我试了下,发现还有一种干扰情况。
0如果出现0.是需要把之前的割舍掉的。然后从新的头开始。具体就不考虑了。

**总结: Array, DP**

My code:

网站地图xml地图