力扣（LeetCode） -152 乘积最大子序列

本题考察的是动态规划

题目描述

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

示例 1：

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

示例 2：

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

题目思考

整数数组中有正数、负数和 0 。我们可以遍历数组，求出到数组中每一个数字的连续乘积的最大值和最小值（之所以要保存最小值，是因为如果遇到负数，越小的数与负数的乘积越大）。怎么求当前数字连续乘积的最大值：如果当前数字为正，则当前数字连续乘积的最大值=Math.max(前一个数字连续乘积的最大值当前数字，当前数字)；如果当前数字为负，则当前数字连续乘积的最大值=Math.max(前一个数字连续乘积的最小值当前数字，当前数字)。

代码

    public int maxProduct(int[] nums) {
    if(nums.length<1) return 0;
    int[][] result = new int[nums.length][2];
    result[0][0] = nums[0];
    result[0][1] = nums[0];
    int max = nums[0];
    for(int i=1; i<nums.length; i++) {
        if(nums[i]<0) {
            result[i][0] = Math.max(result[i-1][1]*nums[i], nums[i]);
            result[i][1] = Math.min(result[i-1][0]*nums[i], nums[i]);
        } else {
            result[i][0] = Math.max(result[i-1][0]*nums[i], nums[i]);
            result[i][1] = Math.min(result[i-1][1]*nums[i], nums[i]);
        }
        max = Math.max(max, result[i][0]);
    }
    return max;
    }