【题目】

一串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;
    }
}