LeetCode Top 100 Liked Questions 152. Maximum Product Subarray (Java版； Medium)

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

welcome to my blog

LeetCode Top 100 Liked Questions 152. Maximum Product Subarray (Java版; Medium)

题目描述

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        if(n==0){
            return 0;
        }
        int res=nums[0];
        //max[i]表示以nums[i]结尾时的最大乘积子数组的乘积
        //max[i] = max(max[i-1]*nums[i], min[i-1]*nums[i], nums[i]);
        int[] max = new int[n];
        int[] min = new int[n];
        max[0] = nums[0];
        min[0] = nums[0];
        for(int i=1; i<n; i++){
            max[i] = Math.max(max[i-1]*nums[i], Math.max(min[i-1]*nums[i], nums[i]));
            min[i] = Math.min(max[i-1]*nums[i], Math.min(min[i-1]*nums[i], nums[i]));

            res = Math.max(res, max[i]);
        }
        return res;
    }
}

第一次做; 动态规划; 回顾子数组动态规划题的规律; 回顾imax,imin的含义: 考虑当前元素的连续子数组的最大值/最小值; 是下面的代码的稍微简洁版

class Solution {
    public int maxProduct(int[] nums) {
        //ensure a non-empty array
        int max = nums[0], imax = nums[0], imin = nums[0];
        for(int i=1; i<nums.length; i++){
            //判断当前元素是否小于零
            if(nums[i] < 0){
                int temp = imax;
                imax = imin;
                imin = temp;
            }
            //更新imax; 以nums[i]为结尾的连续子数组的最大值
            imax = Math.max(imax*nums[i], nums[i]);
            //更新imin; 以nums[i]为结尾的连续子数组的最小值
            imin = Math.min(imin*nums[i], nums[i]);
            //更新max
            max = Math.max(max, imax);
        }
        return max;
    }
}

第一次做; 动态规划; 核心1: 区分连续子数组的最大值imax和全局最大值max的区别; 全局max是到目前为止所有情况的最大值,imax是当前连续子数组(以nums[i]为结尾或者开头)的最大值; 核心2: 当前nums[i]<0时, 交换imax和imin的值; 因为nums[i]<0, 所以imaxnums[i]变成当前连续子数组的最小值, iminnums[i]变成当前连续子数组的最大值; 核心3: 初始化max,imax,imin使用的是nums[0]; 核心4: 关于子数组的动态规划题, 不是选/不选当前状态, 而是一定要考虑当前状态, 选/不选之前的结果, 这相当于子数组动态规划题的一个规律

绊脚案例
int[] arr = {2,3,-2,4};

这个例子说明不仅需要记录imax,还需要记录imin, 因为负负得正
int[] arr2 = {-2,3,-4};

[-1,-2,-9,-6]

class Solution {
    public int maxProduct(int[] nums) {
        if(nums==null || nums.length==0)
            throw new RuntimeException();
        //初始化得小心
        int imin = nums[0], imax = nums[0], max = nums[0];
        for(int i=1; i<nums.length; i++){
            //当前元素小于零则需要交换imax和imin的值
            if(nums[i] < 0){
                int temp = imax;
                imax = imin;
                imin = temp;
            }
            //常规判断; 以nums[i]为结尾/开头的连续子数组的最大值和最小值
            //更新imax; imax含义:以nums[i]为结尾/开头的连续子数组的最大值
            if(imax*nums[i] > nums[i]){
                imax = imax*nums[i];
            }
            else{
                imax = nums[i];
            }
            //更新max
            max = Math.max(max, imax);
            //更新imin; imin含义:以nums[i]为结尾或者开头的连续子数组最小值
            if(imin*nums[i] < nums[i])
                imin = imin*nums[i];
            else
                imin = nums[i];
        }
        return max;
    }
}

题解; 初始化的方式和我的不同; 因为当前元素nums[i]一定会被保留, 所以从nums[0]开始就行

class Solution {
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE, imax = 1, imin = 1;
        for(int i=0; i<nums.length; i++){
            if(nums[i] < 0){ 
              int tmp = imax;
              imax = imin;
              imin = tmp;
            }
            imax = Math.max(imax*nums[i], nums[i]);
            imin = Math.min(imin*nums[i], nums[i]);
            
            max = Math.max(max, imax);
        }
        return max;
    }
}