动态规划-乘积为正数的最长子数组长度.md

title	date	categories	tags
动态规划：乘积为正数的最长子数组长度	2022-07-30 16:25:21 -0700	数据结构与算法 动态规划	动态规划

注意

GitHub 的 Markdown 渲染功能不足，文章的完整渲染欢迎来我的 博客小站 查看~~

题目描述

思路和题解

;;;id1 思路 哈哈哈，这类型题感觉已经渐渐找到诀窍了，实际上就是要分情况讨论，乘积为正数的最长子数组，可以分为若当前 i 是正数，那就要找 i-1 乘积为正数的最大长度；若当前 i 为负数，那就要找 i-1 乘积为负数的最大长度。所以我们就要维护两个数组~~

虽然我已经解出这道题了，但维护两个数组应该还可以再优化一下，和前面的题类型，应该能用滚动数组将空间复杂度从 O(n) 优化到 O(1)，但最近要在外面出差有点忙，所以只能放到以后再优化了，后面的题也只能抽时间再刷~ ;;;

;;;id1 我的题解

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        int len = 0;
        vector<int> pos(n), neg(n);
        if (nums[0] > 0) pos[0] = 1;
        else if (nums[0] < 0) neg[0] = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > 0) {
                if (neg[i-1] > 0) neg[i] = neg[i-1] + 1;
                pos[i] = pos[i-1] + 1;
            }
            else if (nums[i] < 0) {
                neg[i] = pos[i-1] + 1;
                if (neg[i-1] > 0) pos[i] = neg[i-1] + 1;
            }
        }
        return *max_element(pos.begin(), pos.end());
    }
};

;;;