力扣AC：乘积为正数的最长子数组长度 - 动态规划

题目链接

乘积为正数的最长子数组长度

题目描述

实现代码

思路：即dp[i]表示以第i个位置结尾的字符串对应的最长子数组，需要考虑nums[i]为正数和负数的情况；

当nums[i]为正数时，我们应该找第i-1个位置结尾的字符串对应的乘积为负数的最长子数组和；
当nums[i]为负数时，我们应该找第i-1个位置结尾的字符串对应的乘积为整数的最长子数组和；
当nums[i]为0时，值应该为0；因为无论前面是什么，以该位置结尾的值都是0；

因此，我们可以通过positive[i]和negative[i]两个数组分别记录以第i个位置结尾的字符串对应的乘积为正数和负数的最长子数组长度；实现代码如下：

class Solution {
    public int getMaxLen(int[] nums) {
        int length = nums.length;
        int positive = nums[0] > 0 ? 1 : 0;
        int negative = nums[0] < 0 ? 1 : 0;
        int maxLength = positive;
        for (int i = 1; i < length; i++) {
            if (nums[i] > 0) {
                positive++;
                negative = negative > 0 ? negative + 1 : 0;
            } else if (nums[i] < 0) {
                int newPositive = negative > 0 ? negative + 1 : 0;
                int newNegative = positive + 1;
                positive = newPositive;
                negative = newNegative;
            } else {
                positive = 0;
                negative = 0;
            }
            maxLength = Math.max(maxLength, positive);
        }
        return maxLength;
    }
}