Array - 152. Maximum Product Subarray

ppxai

发布于 2020-09-23 17:09:46

2080

发布于 2020-09-23 17:09:46

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.

思路：

这一题是让找出一个字串的乘积最大，因为负数乘负数就是正数，所以在遍历数组找乘积最大的时候同时找一个最大的正数和一个最小的负数，同时记录过程中最大的数，就是结果。

代码：

class Solution {

    public int maxProduct(int[] nums) {

        if (nums == null || nums.length == 0) return 0;
        
        int max = nums[0];
        int min = nums[0];
        int res = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = max;
                max = min;
                min = temp;
            }
            
            max = Math.max(nums[i], max*nums[i]);
            min = Math.min(nums[i], min*nums[i]);
            
            res = Math.max(res, max);
        }
        
        return res;
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019年06月25日，如有侵权请联系 cloudcommunity@tencent.com 删除

input