Chương trình tìm độ dài tối đa của mảng con với tích cực bằng Python

Giả sử chúng ta có một mảng gọi là nums, chúng ta phải tìm độ dài tối đa của một mảng con trong đó tích của tất cả các phần tử của nó là số dương. Chúng ta phải tìm độ dài tối đa của một mảng con có tích cực.

Vì vậy, nếu đầu vào giống như nums =[2, -2, -4,5, -3], thì đầu ra sẽ là 4 vì bốn phần tử đầu tiên đang tạo thành một mảng con có tích số dương.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• Xác định một hàm use (). Điều này sẽ mất s, e
• neg:=0
• ns:=-1, ne:=-1
• đối với tôi trong phạm vi từ s đến e, thực hiện
  • nếu nums [i] <0, thì
    • neg:=neg + 1
    • nếu ns giống -1, thì
      • ns:=i
    • ne:=i
• nếu phủ định là số chẵn, thì
  • trả lại e-s + 1
• nếu không,
  • trả về tối đa e-ns và ne-s
• Từ phương pháp chính, hãy thực hiện như sau -
• ans:=0
• s:=-1, e:=-1
• đối với tôi trong phạm vi từ 0 đến kích thước là num, hãy thực hiện
  • nếu nums [i] không giống 0 và s giống -1, thì
    • s:=i
  • ngược lại khi nums [i] giống 0 và s không giống -1, thì
    • e:=i-1
    • ans:=tối đa ans và use (s, e)
    • s:=-1, e:=-1
• nếu s không giống -1 và e giống -1, thì
  • e:=kích thước của nums -1
  • ans:=tối đa ans và use (s, e)
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

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))

Đầu vào

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

Đầu ra

4