leetcode152. 乘积最大子序列(dp)

àì夳堔傛蜴生んèń 2021-09-28 15:36 318阅读 0赞

给定一个整数数组 `nums` ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

**示例 1:**

输入: [2,3,-2,4]
    输出: 6
    解释: 子数组 [2,3] 有最大乘积 6。

**示例 2:**

输入: [-2,0,-1]
    输出: 0
    解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

package LeetCode;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    
    public class MaxProduct {
            public int maxProduct(int[] nums) {
                if (nums.length <= 0) {
                    return 0;
                }
                //需要存储一个最大值的数组和一个最小的数组
                //最大的数组为了存储最大值
                //最小的数组是为了想要当最小为赋值时如果当前的数字为负数所以他可以是负负为正也可能是最大值
                int[] mins = new int[nums.length];
                int[] maxs = new int[nums.length];
                mins[0]=maxs[0]=nums[0];
                for (int i = 1; i < nums.length ; i++) {
                    if(nums[i]>=0){
                        //当为整数的时候最小值为之前的最小的值乘整数或者是本身
                        //最大值为之前的最大值乘上当前值或者为当前值
                        mins[i]=Math.min(nums[i]*mins[i-1],nums[i]);
                        maxs[i]=Math.max(nums[i]*maxs[i-1],nums[i]);
                    }else{
                        //当为负数时最小的位负数乘之前的最大值
                        //当为负数的时候最大值为负数乘最小的负数
                        mins[i]=Math.min(nums[i]*maxs[i-1],nums[i]);
                        maxs[i]=Math.max(nums[i]*mins[i-1],nums[i]);
                    }
                }
                int res=Integer.MIN_VALUE;
                for (int i = 0; i < nums.length ; i++) {
                    if(res<maxs[i]){
                        res= maxs[i];
                    }
                }
                return res;
    
            }
    
        public static void main(String[] args) {
            MaxProduct m = new MaxProduct();
            int[] a = {-2, 0, -1};
            System.out.println(m.maxProduct(a));
        }
    }