152.Maximum Product Subarray---dp---连续子数组的最大乘积---《编程之美》2.13子数组的最大乘积

题目链接：https://leetcode.com/problems/maximum-product-subarray/description/

题目大意：给出一串数组，找出连续子数组中乘积最大的子数组的乘积。

法一：暴力。竟然能过，数据也太水了。两个for循环，遍历每一个可能的连续子数组，找出最大值。代码如下（耗时161ms）：

     public int maxProduct(int[] nums) {

         int res = Integer.MIN_VALUE, len = nums.length;

         for(int i = 0; i < len; i++) {

             int sum = 1;

             for(int j = i; j < len; j++) {

                 sum *= nums[j];

                 res = Math.max(res, sum);

             }

         }

         return res;

     }

法二（借鉴）：dp，利用两个dp数组，dp_max[i]表示从0到i的数中，子数组乘积最大值，dp_min[i]表示从0到i的数中，子数组乘积最小值，然后每次都更新这两个值，从dp_max数组中取的最大值即可。代码如下（耗时4ms）：

     public int maxProduct(int[] nums) {

         int dp_max[] = new int[nums.length];

         int dp_min[] = new int[nums.length];

         int res = Integer.MIN_VALUE;

         dp_max[0] = nums[0];

         dp_min[0] = nums[0];

         for(int i = 1; i < nums.length; i++) {

             //更新最大值数组

             dp_max[i] = Math.max(Math.max(dp_max[i - 1] * nums[i], dp_min[i - 1] * nums[i]), nums[i]);

             //更新最小值数组

             dp_min[i] = Math.min(Math.min(dp_max[i - 1] * nums[i], dp_min[i - 1] * nums[i]), nums[i]);

             res = Math.max(dp_max[i], res);

         }

         return res;

     }

法三（借鉴）：两次遍历，正向遍历+反向遍历，空间复杂度是o(1)，遇0则归1，否则尽管相乘，找到最大值。代码如下（耗时1ms）;

     public int maxProduct(int[] nums) {

         int res = Integer.MIN_VALUE, sum = 1;

         //正向遍历，取最大值

         for(int i = 0; i < nums.length; i++) {

             sum *= nums[i];

             res = Math.max(res, sum);

             if(nums[i] == 0) {

                 sum = 1;

             }

         }

         //反向遍历，取最大值

         sum = 1;

         for(int i = nums.length - 1; i >= 0; i--) {

             sum *= nums[i];

             res = Math.max(res, sum);

             if(nums[i] == 0) {

                 sum = 1;

             }

         }

         return res;

     }

法四（借鉴）：下面这种方法也是用两个变量来表示当前最大值和最小值的，但是没有无脑比较三个数，而是对于当前的nums[i]值进行了正负情况的讨论：

1. 当遍历到一个正数时，此时的最大值等于之前的最大值乘以这个正数和当前正数中的较大值，此时的最小值等于之前的最小值乘以这个正数和当前正数中的较小值。

2. 当遍历到一个负数或0时，我们先用一个变量t保存之前的最大值mx，然后此时的最大值等于之前最小值乘以这个负数和当前负数中的较大值，此时的最小值等于之前保存的最大值t乘以这个负数和当前负数中的较小值。

3. 在每遍历完一个数时，都要更新最终的最大值。

P.S. 如果这里改成求最小值的话，就是求最小子数组乘积。代码如下（耗时3ms）：

     public int maxProduct(int[] nums) {

         int res = nums[0], ma = nums[0], mi = nums[0];

         for(int i = 1; i < nums.length; i++) {

             if(nums[i] > 0) {

                 ma = Math.max(ma * nums[i], nums[i]);

                 mi = Math.min(mi * nums[i], nums[i]);

             }

             //注意负数或0的情况

             else {

                 int t = ma;

                 ma = Math.max(mi * nums[i], nums[i]);

                 mi = Math.min(t * nums[i], nums[i]);

             }

             res = Math.max(res, ma);

         }

         return res;

     }

法五（借鉴）：在上面的解法中我们分析了当nums[i]为正数时，最大值和最小值的更新情况，为负数时，稍有不同的就是最小值更新时要用到之前的最大值，而不是更新后的最大值，所以我们才要用变量t来保存之前的结果。而下面这种方法的巧妙处在于先判断一个当前数字是否是负数，是的话就交换最大值和最小值。那么此时的mx就是之前的mn，所以mx的更新还是跟上面的方法是统一的，而在在更新mn的时候，之前的mx已经保存到mn中了，而且并没有改变，所以可以直接拿来用。代码如下（耗时1ms）：

     public int maxProduct(int[] nums) {

         int res = nums[0], ma = nums[0], mi = nums[0];

         for(int i = 1; i < nums.length; i++) {

             if(nums[i] <= 0) {

                 int t = ma;

                 ma = mi;

                 mi = t;

             }

             ma = Math.max(ma * nums[i], nums[i]);

             mi = Math.min(mi * nums[i], nums[i]);

             res = Math.max(ma, res);

         }

         return res;

     }

巴特西

152.Maximum Product Subarray---dp---连续子数组的最大乘积---《编程之美》2.13子数组的最大乘积

最新文章

热门文章