โปรแกรมหาความยาวสูงสุดของสับอาร์เรย์ที่ผลคูณเป็นบวกใน Python

โจทย์

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

ตัวอย่าง: nums = [2,-2,-4,5,-3] ผลลัพธ์ 4 เพราะ 4 ตัวแรก [2,-2,-4,5] คูณกันได้บวก

อัลกอริทึม

1. ฟังก์ชันช่วย util(s, e) หาความยาวสับอาร์เรย์สูงสุดในช่วง [s, e] ที่ผลคูณบวก:
   • นับจำนวนค่าลบ (neg) และบันทึกดัชนีแรก (ns) และสุดท้าย (ne) ของค่าลบ
   • ถ้า neg เป็นเลขคู่ คืนความยาวทั้งช่วง e-s+1
   • ถ้าเป็นเลขคี่ คืนค่าสูงสุดระหว่าง e-ns (ตัดค่าลบแรก) และ ne-s (ตัดค่าลบสุดท้าย)
2. ฟังก์ชันหลัก solve(nums):
   • แบ่งอาร์เรย์ด้วย 0 (เพราะ 0 ทำให้ผลคูณเป็น 0 ไม่ใช่บวก)
   • เรียก util() สำหรับแต่ละช่วงที่ไม่มี 0
   • เก็บค่าสูงสุด

ตัวอย่างโค้ด

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, e = -1, -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))  # Output: 4

อินพุต / เอาต์พุต

Input: [2,-2,-4,5,-3]
Output: 4