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

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

class solution
{
public:
    int getResult(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 1)
        {
            return nums[0] > 0 ? 1 : 0;
        }
        
        vector<vector<int>> dp(n + 1, vector<int>(2, 0));
        /*
        dp[i][0] -> negtive
        dp[i][1] -> positive
        */
        int ret = INT_MIN;
        if (nums[0] < 0)
        {
            dp[0][0] = 1;
        }
        else if (nums[0] > 0)
        {
            dp[0][1] = 1;
        }
        
        for (int i = 1; i < n; i++)
        {
            if (nums[i] > 0)
            {
                dp[i][0] = dp[i - 1][0] > 0 ? dp[i - 1][0] + 1 : 0;
                dp[i][1] = dp[i - 1][1] + 1;
            }
            else if (nums[i] < 0)
            {
                dp[i][0] = dp[i - 1][1] + 1;
                dp[i][1] = dp[i - 1][0] > 0 ? dp[i - 1][0] + 1 : 0;
            }
            else
            {
                dp[i][0] = 0;
                dp[i][1] = 0;
            }
            ret = max(ret, dp[i][1]);
        }
        
        return ret;
    }
};

int main()
{
    int n;
    solution mSolution;
    
    while (cin >> n)
    {
        cin.get();
        vector<int> nums(n);
        for (int i = 0; i < n; i++)
        {
            cin >> nums[i];
        }
        cin.get();
        cout << mSolution.getResult(nums) << endl;
    }
    
    return 0;
}

状态优化

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

class solution
{
public:
    int getResult(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 1)
        {
            return nums[0] > 0 ? 1 : 0;
        }
        
        int dpNeg = 0, dpPos = 0;
        
        int ret = INT_MIN;
        if (nums[0] < 0)
        {
            dpNeg = 1;
        }
        else if (nums[0] > 0)
        {
            dpPos = 1;
        }
        
        for (int i = 1; i < n; i++)
        {
            if (nums[i] > 0)
            {
                dpNeg = dpNeg > 0 ? dpNeg + 1 : 0;
                dpPos = dpPos + 1;
            }
            else if (nums[i] < 0)
            {
                int tmp = dpPos + 1;
                dpPos = dpNeg > 0 ? dpNeg + 1 : 0;
                dpNeg = tmp;
            }
            else
            {
                dpNeg = 0;
                dpPos = 0;
            }
            ret = max(ret, dpPos);
        }
        
        return ret;
    }
};

int main()
{
    int n;
    solution mSolution;
    
    while (cin >> n)
    {
        cin.get();
        vector<int> nums(n);
        for (int i = 0; i < n; i++)
        {
            cin >> nums[i];
        }
        cin.get();
        cout << mSolution.getResult(nums) << endl;
    }
    
    return 0;
}