题解 | #乘积为正数的最长连续子数组#

解题思路1：

• 用0分割数组
• 记录每一段的第一个负号和最后一个负号，以及负号的个数
• 对于每一段，如果负号的个数为偶数则此整段就是长度
• 如果负号的个数为奇数，则比较该段开始到第一个负号的长度a和最后一个负号到结尾的长度b。总长度-min（a，b）就是该段的长度
• 比较每段长度取最大值即可。

#include<bits/stdc++.h>
using namespace std;
struct record{
    int start;
    int end;
    vector<int> n_arr;
};
int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i = 0; i< n;++i){
        scanf("%d", &v[i]);
    }
    vector<record> rcds;
    record tmp_rcd;
    tmp_rcd.start = -1;
    int i;
    for(i = 0; i < n; ++i){
        if(v[i] != 0){
            tmp_rcd.end++;
            if(v[i] < 0){
                tmp_rcd.n_arr.push_back(i);
            }
        }
        else{

            tmp_rcd.end = i;
            rcds.push_back(tmp_rcd);

            tmp_rcd.start = i;
            for(auto j=tmp_rcd.n_arr.begin() ;j != tmp_rcd.n_arr.end();){
                tmp_rcd.n_arr.erase(j);
            }
        }
    }
    if (v[i - 1] != 0){
        tmp_rcd.end = i;
        rcds.push_back(tmp_rcd);
        }
    int max_ln = 0;
    for(int i = 0; i < rcds.size(); ++i){
        if (rcds[i].n_arr.size() % 2 == 0){
            max_ln = max(max_ln, rcds[i].end - rcds[i].start - 1);
        }
        else{
            int tmp_ln = rcds[i].end - rcds[i].start - 1;
            tmp_ln = tmp_ln - min(rcds[i].n_arr[0]-rcds[i].start-1, rcds[i].end - rcds[i].n_arr[rcds[i].n_arr.size()-1]-1 ) -1;
            max_ln = max(max_ln, tmp_ln);
        }
    }
    cout<<max_ln<<endl;
    return 0;
}

解题思路2:

• 数组总长度n，i从1到n，在递推的过程中记录当前状态处最长的非零串的长度。并记录该串的正负号，遇到负数*-1即可。
• 取出记录长度中最大的值为正的长度即可。
• 目测可以空间优化。（尚未做）

#include<bits/stdc++.h>
using namespace std;
int solve2(int n, vector<int> & v, vector<pair<int,int>> &dp);
int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    vector<pair<int,int>> dp(n+1,make_pair(INT_MAX, INT_MAX));
    for(int i = 0; i < n; ++i){
        cin>>v[i];
    }
    cout<<solve2(n,v,dp)<<endl;
    return 0;
}
int solve2(int n, vector<int> & v, vector<pair<int,int>> &dp){
    dp[0] = make_pair(0, 0);
    dp[1].first = v[0]!=0;
    if(v[0]>0) dp[1].second = 1;
    else if (v[0]<0) dp[1].second = -1;
    else dp[0].second = 0;
    int ans = 0;
    for(int i = 2; i <= n; ++i){
        if (v[i-1] != 0) dp[i].first = dp[i-1].first+1;
        else dp[i].first = 0;
        if(v[i-1] == 0) dp[i].second = 0;
        else{
            if(dp[i-1].second == 0){
                if(v[i-1]>0) dp[i].second = 1;
                else dp[i].second = -1;
            }
            else {
                if (v[i-1]>0) dp[i].second = dp[i-1].second;
                else dp[i].second = dp[i-1].second*(-1);
            }
        }
        ans = max(ans,dp[i].first*dp[i].second);
    }
    return ans;
}