Leetcode notes - dynamic planning -day6

LeetCode Brush notes - Dynamic programming -day6

152. Product maximum subarray

1. subject

Original link ：152. Product maximum subarray

2. Their thinking

Algorithm ： Dynamic programming + Rolling array optimization

1. f[i] All from 0 To i And choose a[i] The maximum product obtained
2. g[i] All from 0 To i And choose a[i] Minimum product obtained

There are several situations ：

• When a[i] >= 0 when ,f[i] = max(a[i], f[i - 1] * a[i])
• When a[i] < 0 when ,f[i] = max(a[i], g[i - 1] * a[i])
• When a[i] >= 0 when ,g[i] = min(a[i], g[i - 1] * a[i])
• When a[i] < 0 when ,g[i] = min(a[i], f[i - 1] * a[i])

Can be combined into ：

1. When a[i] >= 0 when f[i] = max(a[i], max(f[i-1] * a[i],g[i-1]*a[i]))
2. When a[i]<0 when f[i] = max(a[i], max(g[i-1] * a[i],f[i-1]*a[i])

You can use scrolling arrays to optimize space . See the code for details .

3. Code

class Solution {
    
public:
    int maxProduct(vector<int>& a) {
    
        int f=a[0],g=a[0];
        int res=a[0];
        for(int i=1;i<a.size();i++){
    
            int t=a[i],fa=f*t,ga=g*t;
            f=max(t,max(fa,ga));
            g=min(t,min(fa,ga));
            res=max(res,f);
        }
        return res;
    }
};

1567. The longest subarray length whose product is a positive number

1. subject

Original link ：1567. The longest subarray length whose product is a positive number

2. Their thinking

Algorithm ： Dynamic programming

We can use two arrays f[i] and g[i]：

• f[i] Denotes the following i The length of the longest subarray with a positive product at the end
• g[i] Denotes the following i The length of the longest subarray with a negative product at the end

Here we can get the recurrence formula ：

1. If the current number is greater than 0, namely nums[i]>0, Multiply the previous product by the current number , The positive and negative will not change , therefore ：
   1. f[i]=f[i-1]+1
   2. If g[i-1] It's not equal to 0 Words , One more , If g[i-1] As such 0, A positive number here will not change
2. If the current number is less than 0, namely nums[i]<0, Multiplying the previous product by the current number will change the positive and negative of the product , therefore ：
   1. Now g[i] It should be equal to f[i-1]+1, because f[i-1] The product of contained numbers is a positive number , Multiplying by the current number is just a negative number .
   2. f[i] You need to consider g[i-1] situation , If g[i-1] by 0, here f[i] Also for 0, otherwise f[i]=g[i-1]+1, A negative number multiplied by a negative number is a positive number
3. If the current number is 0, namely nums[i]==0, take f[i],g[i] The assignment is 0
4. Maintain the maximum value for each iteration ：res=max(res,f[i]);

3. Code

class Solution {
    
public:
    int getMaxLen(vector<int>& nums) {
    
        int f=0,g=0;
        if(nums[0]>0) f=1;
        else if(nums[0]<0) g=1;

        int res=f;
        for(int i=1;i<nums.size();i++){
    
            if(nums[i]>0){
    
                f++;
                g=(g==0)?0:g+1;
            }else if(nums[i]<0){
    
                int t=f;
                f=(g==0)?0:g+1;
                g=t+1;
            }else{
    
                f=0,g=0;
            }
            res=max(res,f);
        }
        return res;
    }
};