Welcome to Subscribe On Youtube

1567. Maximum Length of Subarray With Positive Product

Description

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return the maximum length of a subarray with positive product.

 

Example 1:

Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.

Example 2:

Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.

Example 3:

Input: nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

 

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

Solutions

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int getMaxLen(int[] nums) {
          int f1 = nums[0] > 0 ? 1 : 0;
          int f2 = nums[0] < 0 ? 1 : 0;
          int res = f1;
          for (int i = 1; i < nums.length; ++i) {
              if (nums[i] > 0) {
                  ++f1;
                  f2 = f2 > 0 ? f2 + 1 : 0;
              } else if (nums[i] < 0) {
                  int pf1 = f1, pf2 = f2;
                  f2 = pf1 + 1;
                  f1 = pf2 > 0 ? pf2 + 1 : 0;
              } else {
                  f1 = 0;
                  f2 = 0;
              }
              res = Math.max(res, f1);
          }
          return res;
      }
  }
  

• class Solution {
  public:
      int getMaxLen(vector<int>& nums) {
          int f1 = nums[0] > 0 ? 1 : 0;
          int f2 = nums[0] < 0 ? 1 : 0;
          int res = f1;
          for (int i = 1; i < nums.size(); ++i) {
              if (nums[i] > 0) {
                  ++f1;
                  f2 = f2 > 0 ? f2 + 1 : 0;
              } else if (nums[i] < 0) {
                  int pf1 = f1, pf2 = f2;
                  f2 = pf1 + 1;
                  f1 = pf2 > 0 ? pf2 + 1 : 0;
              } else {
                  f1 = 0;
                  f2 = 0;
              }
              res = max(res, f1);
          }
          return res;
      }
  };
  

• class Solution:
      def getMaxLen(self, nums: List[int]) -> int:
          f1 = 1 if nums[0] > 0 else 0
          f2 = 1 if nums[0] < 0 else 0
          res = f1
          for num in nums[1:]:
              pf1, pf2 = f1, f2
              if num > 0:
                  f1 += 1
                  if f2 > 0:
                      f2 += 1
                  else:
                      f2 = 0
              elif num < 0:
                  pf1, pf2 = f1, f2
                  f2 = pf1 + 1
                  if pf2 > 0:
                      f1 = pf2 + 1
                  else:
                      f1 = 0
              else:
                  f1 = 0
                  f2 = 0
              res = max(res, f1)
          return res
  
  

• func getMaxLen(nums []int) int {
  	f1, f2 := 0, 0
  	if nums[0] > 0 {
  		f1 = 1
  	}
  	if nums[0] < 0 {
  		f2 = 1
  	}
  	res := f1
  	for i := 1; i < len(nums); i++ {
  		if nums[i] > 0 {
  			f1++
  			if f2 > 0 {
  				f2++
  			} else {
  				f2 = 0
  			}
  		} else if nums[i] < 0 {
  			pf1, pf2 := f1, f2
  			f2 = pf1 + 1
  			if pf2 > 0 {
  				f1 = pf2 + 1
  			} else {
  				f1 = 0
  			}
  		} else {
  			f1, f2 = 0, 0
  		}
  		res = max(res, f1)
  	}
  	return res
  }
  

• function getMaxLen(nums: number[]): number {
      // 连续正数计数n1, 连续负数计数n2
      let n1 = nums[0] > 0 ? 1 : 0,
          n2 = nums[0] < 0 ? 1 : 0;
      let ans = n1;
      for (let i = 1; i < nums.length; ++i) {
          let cur = nums[i];
          if (cur == 0) {
              (n1 = 0), (n2 = 0);
          } else if (cur > 0) {
              ++n1;
              n2 = n2 > 0 ? n2 + 1 : 0;
          } else {
              let t1 = n1,
                  t2 = n2;
              n1 = t2 > 0 ? t2 + 1 : 0;
              n2 = t1 + 1;
          }
          ans = Math.max(ans, n1);
      }
      return ans;
  }
  
  

All Problems

All Solutions