โปรแกรมค้นหาความยาวสูงสุดของ subarray ด้วยผลคูณบวกใน Python

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums เราต้องหาความยาวสูงสุดของ subarray โดยที่ผลคูณขององค์ประกอบทั้งหมดเป็นค่าบวก เราต้องหาความยาวสูงสุดของอาร์เรย์ย่อยที่มีผลคูณบวก

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2,-2,-4,5,-3] ผลลัพธ์จะเป็น 4 เนื่องจากองค์ประกอบสี่ตัวแรกสร้างอาร์เรย์ย่อยที่มีผลลัพธ์เป็นบวก

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ :

• กำหนดฟังก์ชัน util() นี่จะใช้เวลา s, e
• เนก :=0
• ns :=-1, ne :=-1
• สำหรับฉันอยู่ในช่วง s ถึง e ทำ
  • ถ้า nums[i] <0 แล้ว
    • neg :=neg + 1
    • ถ้า ns เหมือนกับ -1 แล้ว
      • ns :=ฉัน
    • เน :=ฉัน
• ถ้า neg เท่ากัน
  • ส่งคืน e-s+1
• มิฉะนั้น
  • คืนค่าสูงสุดของ e-ns และ ne-s
• จากวิธีหลัก ให้ทำดังต่อไปนี้ −
• ตอบ :=0
• s :=-1, e :=-1
• สำหรับ i ในช่วง 0 ถึงขนาดของ nums ให้ทำ
  • ถ้า nums[i] ไม่เหมือนกับ 0 และ s เหมือนกับ -1 แล้ว
    • s :=ฉัน
  • มิฉะนั้น เมื่อ 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