Python程式：查詢正積子陣列的最大長度

假設我們有一個名為nums的陣列，我們需要找到一個子陣列的最大長度，其中所有元素的乘積為正。我們需要找到一個正積子陣列的最大長度。

因此，如果輸入類似於 nums = [2,-2,-4,5,-3]，則輸出將為 4，因為前四個元素形成了一個乘積為正的子陣列。

為了解決這個問題，我們將遵循以下步驟

• 定義一個函式 util()。這將接收 s、e 作為引數
• neg := 0
• ns := -1, ne := -1
• 對於從 s 到 e 的範圍內的 i，執行以下操作：
  • 如果 nums[i] < 0，則
    • neg := neg + 1
    • 如果 ns 等於 -1，則
      • ns := i
    • ne := i
• 如果 neg 為偶數，則
  • 返回 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) 中的最大值
• 返回 ans

讓我們看看下面的實現以獲得更好的理解

示例

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

Arnab Chakraborty

更新時間: 2021年10月4日

221 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始