乘积最大子数组

问题陈述

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

思路分析

我们只要记录前i的最小值, 和最大值, 那么 dp[i] = max(nums[i] * pre_max, nums[i] * pre_min, nums[i]), 这里0 不需要单独考虑, 因为当相乘不管最大值和最小值,都会置0

代码实现

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution{
    public int maxProduct(int[] nums){
        int preMin=nums[0],preMax=nums[0],res=nums[0];
        int temp1=0,temp2=0;
        for(int i=1;i<nums.length;i++){
            temp1=preMin*nums[i];//若之前为负数，当前数也为负数
            temp2=preMax*nums[i];
            preMax=Math.max(Math.max(temp1,temp2),nums[i]);
            preMin=Math.min(Math.max(temp1,temp2),nums[i]);
            res=Math.max(res,preMax);//
        }
        return res;
    }
}