152. Maximum Product Subarray

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: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

难度:medium

题目:给定整数数组,找出乘积最大的子数组。

思路:结合最大子数组和,这里用两个变量分别记下包含当前元素的最大乘积和最小乘积,因为下一个元素正负不定。

Runtime: 2 ms, faster than 74.69% of Java online submissions for Maximum Product Subarray.

Memory Usage: 37.6 MB, less than 100.00% of Java online submissions for Maximum Product Subarray.

public class Solution {
    public int maxProduct(int[] nums) {
        if (null == nums || nums.length < 1) {
            return 0;
        }
        
        int maxVal = nums[0];
        int curMaxVal = nums[0], curMinVal = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int pCurMinVal = curMinVal;
            int pCurMaxVal = curMaxVal;

            curMaxVal = Math.max(Math.max(nums[i], curMaxVal * nums[i]), pCurMinVal * nums[i]);
            curMinVal = Math.min(Math.min(nums[i], curMinVal * nums[i]), pCurMaxVal * nums[i]);
            
            maxVal = Math.max(maxVal, curMaxVal);
        }
        
        return maxVal;
    }
}

原文 

https://segmentfault.com/a/1190000018154455

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 152. Maximum Product Subarray

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址