Introduction to leetcode 21 day dynamic programming -- from 0 to 0.5 [Day06] maximum subarray of product and maximum subarray length dp optimization with positive product

DAY06

Write in front

Today is the sixth day of the introduction to dynamic planning. Today's question is a little difficult, and relevant optimization needs to be considered. If you feel uncomfortable, just master the simplest method. Recently, bloggers are learning some technologies. These days, they may only temporarily update the daily question and the introduction to dynamic planning, The basic knowledge of Java may be updated during the blogger's holiday next month (around January 7). Thank you. At the same time, Xiaofu also understands that the technical knowledge not only needs to understand the basic knowledge, but also needs to expand the possible situations in the future business. Xiaofu will improve one by one in the future. Without saying much, it will be over!

subject

Topic 1

1. Product maximum subarray

Give you an array of integers nums ，Please find the continuous sub array with the largest product in the array
(The subarray contains at least one number) and returns the product corresponding to the subarray.

Example

Example 1:

input: [2,3,-2,4]
output: 6
 explain: Subarray [2,3] There is a maximum product of 6.

Example 2:

input: [-2,0,-1]
output: 0
 explain: The result cannot be 2, because [-2,-1] Not a subarray.

thinking

After several days of dynamic planning training, you should get started with the basic idea,
However, for this problem, although the previous thought can still be applied, it is almost unsatisfied
 The demand for time and space goes against the original intention of our learning algorithm,
But the simplest idea is to:
1)Can you maintain only one array today dp Well,
Because you have to consider that if the current product sum is the product sum of the smallest array,
If the next number is negative and then multiplied, you will get a relatively large value,
Compare it with the product sum of the largest subarray to get the maximum value.
2)Similarly, if the product sum of the largest subarray is obtained at this time,
If the next number is negative and then multiplied, a relatively small value will be obtained,
Therefore, it is necessary to constantly compare when scrolling with the array,
It will greatly increase the complexity of time and space.

Dynamic transformation equation:
Used to get the maximum value of the current product:
dpMax[i] = Math.max(nums[i], Math.max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]));
Used to get the minimum value of the current product:
dpMin[i] = Math.min(nums[i], Math.min(dpMin[i - 1] * nums[i], dpMax[i - 1] * nums[i]));

code implementation

class Solution {
    public int maxProduct(int[] nums) {
       int res = nums[0];
       int[] dpMax = new int[nums.length + 1], dpMin = new int [nums.length + 1];
       dpMax[0] = nums[0];  // Initialize two dp arrays
       dpMin[0] = nums[0];
       for(int i = 1; i < nums.length; i++)
       { 
           dpMax[i] = Math.max(nums[i], Math.max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i])); //Gets the maximum value of the product
           dpMin[i] = Math.min(nums[i], Math.min(dpMin[i - 1] * nums[i], dpMax[i - 1] * nums[i])); //Gets the minimum value of the product
           res = Math.max(res, dpMax[i]);
       }         
       return res;   
    }
}

results of enforcement

Not yet. My dog eats less and runs faster~

optimization

Since the above ideas mentioned that maintaining arrays consumes a lot of space and time, we can use variables to simulate the current situation, so as to save space and time

class Solution {
    public int maxProduct(int[] nums) {
    	//Design imax and imin to obtain the maximum and minimum values of the current sub array
        int max = nums[0],imax = 1 ,imin = 1;
        for (int i = 0 ; i< nums.length ;i++){
        	//If the current number to be multiplied is less than 0, the maximum will become the minimum, and it will be exchanged to facilitate variable processing
            if (nums[i] < 0){
                int temp = imax ;
                imax = imin;
                imin = temp;
            }
            //If the current number to be multiplied is < 0, the maximum will become the minimum and the minimum will become the maximum
            imax = Math.max(imax*nums[i],nums[i]);
            imin = Math.min(imin*nums[i],nums[i]);

            max = Math.max(imax,max);
        }
        return max;

    }
}

Optimization results

Topic 2

Example

Example 1:

Input: nums = [1,-2,-3,4]
Output: 4
 Explanation: the product of the array itself is a positive number with a value of 24.

Example 2:

Input: nums = [1,-2,-3,4]
Output: 4
 Explanation: the product of the array itself is a positive number with a value of 24.

Example 3:

Input: nums = [-1,-2,-3,0,1]
Output: 2
 Explanation: the longest subarray whose product is a positive number is [-1,-2] perhaps [-2,-3] . 

Example 4:

Input: nums = [-1,2]
Output: 1

Tips

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

thinking

This problem needs to be discussed in categories
1)If the current value to be multiplied is equal to 0, the length of the positive and negative longest subarray needs to be reset to zero
 Re traverse from the next number
2)When the multiplier is positive at this time, the positive sub array and length maintained at this time+1
 And you need to prepare for the next negative multiplier, so that the length of the negative number can be reduced+1
3)If the current multiplier is negative, you need to record the length of the sub array of the current positive number first,
At this time, the length of the positive subarray needs to be prepared for the next negative number+1

code implementation

class Solution {
    public int getMaxLen(int[] nums) {
    	//Maintain the current positive sub array length and negative sub array length
        int posLen = 0;
        int negLen = 0;
        int max = 0;
        //Ergodic classification discussion
        for (int i : nums){
            if (i == 0){
                posLen = 0;
                negLen = 0;
                continue;
            }
            //When the current multiplier is greater than 0
            if (i > 0){
                posLen++;
                negLen = negLen == 0? 0:negLen+1;
            }
			//When the current multiplier is less than 0
            if (i < 0){
                int temp = posLen;
                posLen = negLen == 0 ? 0 :negLen+1;
                negLen = temp+1;
            }
            //The scroll variable is used to record the maximum value
            max = Math.max(max,posLen);
        }
        return max;
    }
}

results of enforcement

Write at the end

Today's dynamic planning has changed a lot compared with yesterday,
You can no longer maintain the value of the required solution through an array or variable,
We also need to classify and discuss the problem through the relevant knowledge of mathematics
Stick to clock in for the sixth day~
Come on~

last

Make progress every day and harvest every day

May you succeed in your career and learn

If you feel good, don't forget to click three times~