Niuke network: longest continuous subarray with positive product

1. Non ring

  Pay attention to the examination ！！

Here is the length of the longest continuous product to be a positive number , We maintain two lengths , One pos One neg,pos Represents the product of the longest positive number up to the current number ,neg Represents the product of the longest negative number up to the current number , We do the following for each number :

1. If the current number is positive , Then the length of the longest positive sequence can be increased by one , If there is the longest negative sequence , Plus one

2. If the current number is 0, Then the longest positive and negative sequences of all sequences ending with this number are 0, Therefore, all are updated to 0

3. If the current number is negative , You need to exchange pos and neg

The specific code is as follows ：

#include<bits/stdc++.h>
using namespace std;
int dp(vector<int> &nums){
    int res=0;
    int pos=nums[0]>0 ? 1: 0;
    int neg=nums[0]<0 ? 1: 0;
    for(int i=1;i<nums.size();++i){
        if(nums[i]>0){
            pos=pos+1;
            neg=neg>0 ? neg+1 : 0;
        }else if(nums[i]==0){
            pos=neg=0;
        }else{
            int tmp=neg>0 ? neg+1:0;
            neg=pos+1;
            pos=tmp;
        }
        res=max(res,pos);
    }
    return res;
}

int main(){
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0;i<n;++i){
        cin>>nums[i];
    }
    cout<<dp(nums)<<endl;
    return 0;
}

2. Ring array

  The idea here refers to the answers in Niuke .

First , We all know how to find the maximum sum of acyclic arrays , It's just linear dp, The maximum length of each update that ends with the current number , So what if it's cyclic ？ Each time we use a new starting point to do linear dp We can work out .

The specific code is as follows ：

#include<bits/stdc++.h>// Timeout code 
using namespace std;
int solve(int n, vector<int> &v, vector<int> &dp);
int process2(int start, vector<int>&v);
int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i){
        scanf("%d",&v[i]);
    }
    vector<int> dp(n, INT_MIN);
    cout<<solve(n,v, dp)<<endl;
    return 0;
}
int solve(int n, vector<int> &v, vector<int> &dp){
    int ans = process2(0, v);
    for(int i = 1; i < n; ++i){
        ans = max(ans,process2(i,v));
    }
    return ans;
}
int process2(int start, vector<int>&v){
    int ans = v[start];
    for(int i = 1; i < v.size(); ++i){
        ans = max(ans+v[(start + i)%v.size()],v[(start+i)%v.size()]);
    }
    return ans;
}

The time complexity is zero O(n^2), Will timeout .

• Switch views , According to the general idea of maximum continuous sum , That is to say dp Can get the largest continuous subarray and .
• Empathy , If we find the sum of the smallest continuous subarray , You will find a feature .
• Hypothetical use sum Record the sum of the entire array , Then the largest continuous subarray and dpmax And minimum continuous subarray dpmin And must be connected , Because suppose you don't want to connect , The middle paragraph is either larger than 0, Then it should belong to the largest subarray continuous sum , Otherwise it should belong to the smallest continuous subarray and .
• So we finally get sum,dpmax,dpmin It can be judged later . hypothesis dpmax+dpmin<sum This means that the sum of the endpoints on both sides of the array is positive , So this part should be left to (dpmax=sum−dpmin), Otherwise go straight back to dpmax that will do , Of course, there is a special case （ Initializing dpmax The first value of the array is given v[0], If it is negative , There must be dpmax+dpmin<sum Therefore, this place should be judged specially , If dpmax<0 Just go back ）

The idea is as follows ：
1. With ring ： First, find out the minimum value of continuous subarray in the case of acyclic res2, Then use an array and sum Subtract the minimum res2 That is, the maximum value of the continuous subarray in the ring case
2. Acyclic case ： Maximum subarray and
3. The largest circular subarray and = max( Maximum subarray and , The sum of the arrays - Minimal array and ), To exclude all negative numbers = Maximum subarray and
Link to the original text ：https://blog.csdn.net/qq_35915636/article/details/123974337

#include<bits/stdc++.h>
using namespace std;
int dp(vector<int> &nums){
    int sum, dpmx, dpmn, mx, mn;
    dpmx=dpmn=mx=mn=sum=nums[0];
    for(int i=1;i<nums.size();++i){
        mx=max(mx+nums[i],nums[i]);
        mn=min(mn+nums[i],nums[i]);
        dpmx=max(dpmx, mx);
        dpmn=min(dpmn, mn);
        sum+=nums[i];
    }
    if(dpmx<0) return dpmx;
    if(dpmx+dpmn<sum) dpmx=sum-dpmn;
    return dpmx;
}

int main(){
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0;i<n;++i){
        cin>>nums[i];
    }
    cout<<dp(nums)<<endl;
    return 0;
}