Pythonで正の積を持つサブ配列の最大長を見つけるプログラム

numsという配列があるとすると、そのすべての要素の積が正であるサブ配列の最大長を見つける必要があります。正の積を持つサブアレイの最大長を見つける必要があります。

したがって、入力がnums =[2、-2、-4,5、-3]の場合、最初の4つの要素が正の積のサブ配列を形成しているため、出力は4になります。

これを解決するには、次の手順に従います：

• 関数util（）を定義します。これには時間がかかります、e
• neg：=0
• ns：=-1、ne：=-1
• sからeの範囲のiについては、
  • nums [i] <0の場合、
    • neg：=neg + 1
    • nsが-1と同じ場合、
      • ns：=i
    • ne：=i
• 負の値が偶数の場合、
  • return e-s + 1
• それ以外の場合、
  • e-nsとne-sの最大値を返す
• メインの方法から、次の手順を実行します-
• ans：=0
• s：=-1、e：=-1
• 0からnumsのサイズの範囲のiの場合は、
  • nums [i]が0と同じでなく、sが-1と同じである場合、
    • s：=i
  • それ以外の場合、nums [i]が0と同じで、sが-1と同じでない場合、
    • e：=i-1
    • ans：=ansとutil（s、e）の最大数
    • s：=-1、e：=-1
• sが-1と同じでなく、eが-1と同じである場合、
  • e：=numsのサイズ-1
  • ans：=ansとutil（s、e）の最大数
• 回答を返す

理解を深めるために、次の実装を見てみましょう。

例

def util(s, e):
   neg = 0
   ns, ne = -1, -1
   for i in range(s, e+1):
      if nums[i]<0:
         neg += 1
         if ns == -1:
            ns = i
         ne = i

   if neg == 0 or neg %2 == 0:
      return e-s+1
   else:
      return max(e-ns, ne-s)

def solve(nums):
   ans = 0
   s, e = -1, -1

   for i in range(len(nums)):
      if nums[i]!=0 and s == -1:
         s = i
      elif nums[i]==0 and s != -1:
         e = i-1
         ans = max(ans, util(s, e))
         s = -1
         e = -1

   if s!= -1 and e == -1:
      e = len(nums)-1
      ans = max(ans, util(s, e))
      return ans

nums = [2,-2,-4,5,-3]
print(solve(nums))

入力

[2,-2,-4,5,-3]

出力

4