Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

The title

Given an integer array nums, find the non-empty continuous subarray with the largest product (that subarray contains at least one number) and return the product of that subarray. The answer to the test case is a 32-bit integer. A subarray is a continuous sequence of subarrays.

Example 1:

Input: nums = [2,3,-2,4] output: 6 explanation: the subarray [2,3] has a maximum product of 6.Copy the code

Example 2:

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

Tip:

1 <= nums.length <= 2 * 104-10 <= nums[I] <= 10 Nums is guaranteed to be a 32-bit integerCopy the code

Answer key

Analysis of the problem solving

Antithesis thought

  1. This problem is a typical dynamic programming problem;
  2. We need to constantly iterate through the array to get the maximummaxF = Math.max(mx * nums[i], nums[i]);;
  3. Due to theThe presence of negative numbers in the array may cause the largest value to become a minimum and the minimum to become a maximum. So you also need to maintain the current minimum

minF = Math.min(mn * nums[i], nums[i]); 4. If negative numbers appear, min and Max will be exchanged before further calculation;

Complexity analysis

  • Time complexity: O(N)
  • Space complexity: O(1)

The problem solving code

The solution code is as follows (there are detailed notes in the code) :

class Solution {
    public int maxProduct(int[] nums) {
        // maxF Max, minF min, ans result
        int maxF = nums[0], minF = nums[0], ans = nums[0];
        // Array length
        int len = nums.length;
        for (int i =1; i < len; i++) {
            // Save old data
            int mx = maxF , mn = minF;
            // Update the maximum value
            maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
            // Update the minimum value
            minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
            // Update the result
            ans = Math.max(maxF, ans);
        }
        / / return
        returnans; }}Copy the code

Feedback results after submission:

The reference information

  • Force buckle (LeetCode) 152. Product maximum subarray