转载

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

正文到此结束