1567 Given an array of integers, nums, ask you to find the length of the array of integers whose product is positive. A subarray of an array is an array of zero or more consecutive numbers from the original array. Return the maximum array length whose product is positive. Example 1: Input: nums = [1,-2,-3,4] Output: 4 Explanation: The product of the array itself is a positive number with the value 24.

Example 2: input: nums = [0,1,-2,-3,-4] output: 3 description: the longest subarray whose product is positive is [1,-2,-3], whose product is 6. Notice, we can’t include 0 in the subarray, because then the product is 0, not positive.

Example 3: Input: nums = [-1,-2,-3,0,1] Output: 2 Description: The largest array whose product is positive is either [-1,-2] or [-2,-3].

Example 4: Input: nums = [-1,2] Output: 1

Example 5: input: nums = [1,2,3,5, 6,4,0,10] output: 4

1 <= nums.length <= 10^5 -10^9 <= nums[I] <= 10^9

So instead of trying to figure out the length of the longest contiguous subarray, you can think about using dynamic programming recursion. If the product is positive, you can divide it into two cases, a positive number times a positive number, or a negative number times a negative number, use each casepos[i] 和 neg[i]To represent the elementsiThe length of the ending subarray.pos[0] 和 neg[0]The value of depends on the positive or negative of the first element. There are three cases of recursion:

The code is as follows:

class Solution { public int getMaxLen(int[] nums) { int n = nums.length; int[] pos = new int[n]; int[] neg = new int[n]; pos[0] = (nums[0] > 0) ? 1:0; neg[0] = (nums[0] < 0) ? 1:0; int ans = pos[0]; for (int i = 1; i < n; i++) { if (nums[i] > 0) { pos[i] = pos[i - 1] + 1; neg[i] = (neg[i - 1] > 0) ? neg[i - 1] + 1 : 0; } else if (nums[i] < 0) { pos[i] = (neg[i - 1] > 0) ? neg[i - 1] + 1 : 0; neg[i] = pos[i - 1] + 1; } else { pos[i] = 0; neg[i] = 0; } ans = Math.max(ans, pos[i]); } return ans; }}Copy the code

In fact, in the recursion process, the current state is only related to the previous state, and a variable can be used to record the previous state. The space-optimized code is as follows:

class Solution { public int getMaxLen(int[] nums) { int n = nums.length; int pos = (nums[0] > 0) ? 1:0; int neg = (nums[0] < 0) ? 1:0; int ans = pos; for (int i = 1; i < n; i++) { if (nums[i] > 0) { pos = pos + 1; neg = (neg > 0) ? neg + 1 : 0; } else if (nums[i] < 0) { int lastPos = pos; pos = (neg > 0) ? neg + 1 : 0; neg = lastPos + 1; } else { pos = 0; neg = 0; } ans = Math.max(ans, pos); } return ans; }}Copy the code

Time complexity: O(n), where n is the length of the array; Space complexity: The optimized space complexity is O(1).