Leetcode # 1567. Maximum Length of Subarray With Positive Product

2021.12.27
LeetCode

https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/

Solution

把 nums 以 0 分割為 part[0], part[1], …

如果 len(part[i]) % 2 為 0
（負數有偶數個，則其積為正）
part[i] 的 Maximum Length of Subarray With Positive Product 為 len(part[i])
如果 len(part[i]) % 2 不為 0 ：
1. 起始為正數，結束也為正數，即
  \begin{align}
  & part[i][j] > 0, \forall j \in [0, x] \land part[i][x + 1]<0 \\
  & part[i][j] > 0, \forall j \in [y, \text{len}(part[i]) – 1] \land part[i][y – 1]<0
  \end{align}
  則其 Maximum Length of Subarray With Positive Product
  為 len(part[i]) – min(x + 1, len(part[i]) – y) – 1
  （拿掉頭尾的連續正數較短之其一及一個負數）
2. 起始或結束有其一為負數
  則其 Maximum Length of Subarray With Positive Product 為 len(part[i]) – 1
  （拿掉頭或尾的一個負數）

class Solution:
  def getMaxLen(self, nums: List[int]) -> int:
    last_sign = 0
    same_signs_n = 1
    record_about_signs = [] # length of this non-zero numbers sequence, 
                            # length of positive numbers sequence at first, 
                            # length of negative numbers sequence at first
                            # number of negative numbers
    
    for i, num in enumerate(nums):
      sign = 0 if num == 0 else (1 if num > 0 else -1)
      
      # when sign is changed from 0 to non-zero number, 
      # append new part into record_about_signs
      
      # when first time sign is changed and last_sign is 1, 
      # write record_about_signs[-1][1]
      if sign != last_sign:
        if last_sign == 0:
          record_about_signs.append([0, -1, 0, 0])
        
        elif record_about_signs[-1][1] == -1:
          record_about_signs[-1][1] = same_signs_n if last_sign == 1 else 0
          
      
      # when num is changed from positive number to 0 or num is last element, 
      # write record_about_signs[-1][2]
      if (last_sign == 1 and num == 0) or (sign == 1 and i == len(nums) - 1):
        record_about_signs[-1][2] = (same_signs_n if last_sign == 1 else 0) \
                                    + (1 if sign == 1 else 0)
      
      if num != 0:
        record_about_signs[-1][0] += 0 if num == 0 else 1
        record_about_signs[-1][3] += 1 if sign == -1 else 0 
        same_signs_n = (same_signs_n + 1) if sign == last_sign else 1
      last_sign = sign
      
    # print(record_about_signs)

    ans = 0
    for record_about_sign in record_about_signs:

      if record_about_sign[3] % 2 == 0:
        ans = max(ans, record_about_sign[0])
      elif record_about_sign[1] > 0 and record_about_sign[2] > 0:
        ans = max(ans, record_about_sign[0] \
              - min(record_about_sign[1], record_about_sign[2]) - 1)
      else:
        ans = max(ans, record_about_sign[0] - 1)

    return ans

Last Updated on 2023/08/16 by A1go