[Leetcode 152]最大乘积子串Maximum Product Subarray 踩坑

【题目】

一串int数组中找到乘积最大的子串,子串必须连续,返回成绩ans

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

 

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

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

【思路】

分类讨论,int类型有正数、负数、0。主要讨论负数的情况,奇数个&偶数个

考虑到负负得正的情况,需要将负数保留,所以使用min、max进行存储

遍历数组时,

当前最大值=max(最大值,最小值*当前数,当前数)

当前最小值=min(最小值,最小值*当前数,当前数)

当前ans=max(当前最大值,ans)

 

【代码】

注意坑:不要嫌麻烦直接写max(cur,Math.max(cur*max,cur*min))!!这轮的min max是由上轮的min max及乘积决定,先算max时没关系,再算min时,max的值已经更新成这轮的了。

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;

        int max=nums[0]; int min=nums[0]; int ans=nums[0];
        for(int i=1;i<nums.length;i++){
            int cur=nums[i];
            int tmpMax=cur*max;
            int tmpMin=cur*min;

            max=Math.max(cur,Math.max(tmpMax,tmpMin));
            min=Math.min(cur,Math.min(tmpMax,tmpMin));

            ans=Math.max(ans,max);

        }
        return ans;
    }
}

 

[Leetcode 152]最大乘积子串Maximum Product Subarray 踩坑

上一篇:tomcat安装部署


下一篇:setState 数据合并