乘积最大子数组

题目描述

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

示例 1:

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

示例 2:

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

思路

可以维护两个DP,表示最大值和最小值（因为数据中包含正负),转移方程为$maxDP[i+1] = max(nums[i+1], maxDP[i+1]*nums[i+1], minDP[i+1]*nums[i+1])$以及$minDP[i+1] = min(nums[i+1], maxDP[i+1]*nums[i+1], minDP[i+1]*nums[i+1])$,由于只涉及DP的两个状态值，所以去除掉所有状态的存储，只存储上一状态即可。

代码

class Solution {
    public int maxProduct(int[] nums) {
        int result = nums[0];
        int maxNum = 1;
        int minNum = 1;
        for(int i = 0; i < nums.length; i++){
            if (nums[i] < 0){
                maxNum = maxNum + minNum;
                minNum = maxNum - minNum;
                maxNum = maxNum - minNum;
            }
            maxNum = nums[i] > maxNum * nums[i] ? nums[i]: maxNum * nums[i];
            minNum = nums[i] < minNum * nums[i] ? nums[i]: minNum * nums[i];
            if(result < maxNum){
                result = maxNum;
            }
        }
        return result;
    }
}