Given an array of integers, nums, find the contiguous subarray with the largest product (that subarray contains at least one number) and return the product of that subarray.

Example 1:

Input:2.3, -2.4] output:6Explanation: Subarray [2.3] has maximum product6.Copy the code

Example 2:

Input: [...2.0, -1] output:0Explanation: The result cannot be2Because [...2, -1] is not a subarray.Copy the code

If they want to find the product of the subarray with the largest product in the array, what do they do? Of course, we need to find all possible subarrays that can be formed by the elements of the array, then multiply each subarray, and return the maximum product. Solving this problem requires backtracking to find every possible subarray.

However, this problem requires that the subarray must be continuous. If the backtracking method is continued, then the judgment logic of whether the subarray is continuous needs to be added. Since the time complexity of the backtracking method itself is very high, adding additional logic will further increase the complexity, which is not the optimal solution.

For the continuous subarray problem, when traversing a certain position in the array, its change in the result is only related to the previous position. Therefore, it can be solved using dynamic programming. But the elements of an array are both positive and negative, so the product of the corresponding continuous subarrays is also positive and negative. Assuming that Max and min represent the current maximum and minimum value of the product, respectively, for a specific position:

  • If the current positionnums[i] > 0, there aremax = MAX(max * nums[i], nums[i).min = MIN(min * nums[i], nums[i])
  • If the current positionnums[i] < 0, thenmaxandminIt needs to be exchanged, guaranteedmaxandminAgain, we’re going to store the maximum and minimum of the product

Java solution code is as follows:

class Solution {
    public int max = 1;
    public int min = 1;
    public int res = Integer.MIN_VALUE;
    
    public int maxProduct(int[] nums) {
        if(nums == null) {return 0;
        }

        for(int i = 0; i < nums.length; i++){
            if(nums[i] < 0){
                swap();
            }

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

    public void swap(a){
       inttemp = max; max = min; min = temp; }}Copy the code