152. Maximum Product Subarray

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.
题目:返回数组中连续的最大值。
思路:用一维动态规划中的“局部最优和全局最优法”。利用乘法性质:累加结果只要是正的一定是递增,乘法中有可能现在看起来小的一个负数,后面跟另一个负数相乘就会得到最大的乘积。所以,只需要在维护一个局部最大的同时,在维护一个局部最小,这样如果下一个元素遇到负数时,就有可能与这个最小相乘得到当前最大的乘积和。

 /**
 * @param {number[]} nums
 * @return {number}
 */
       var maxProduct = function(nums) {
          var i , j;
          var len = nums.length;
          var max = 0;
          var min = 0;
          var result = 0;
          var temp_max = 0;
          if(nums.length==0) return 0;
          else if(nums.length==1) return Number(nums);
          max = nums[0];
          min = nums[0];
          result = nums[0];
          for(i=1;i<nums.length;i++)
          {
              temp_max = max;
              max = Math.max(Math.max(nums[i]*max,nums[i]),nums[i]*min);
              min = Math.min(Math.min(nums[i]*temp_max,nums[i]),nums[i]*min);
              result = Math.max(result,max);
          }
          return result;
       };
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容