โปรแกรมหาความยาว subsequence สลับเครื่องหมายมากสุดใน Python

สมมติว่ามีรายการตัวเลข nums ต้องการหาความยาว subsequence ยาวสุดที่เครื่องหมายสลับกันทุกคู่ติดกัน

ตัวอย่าง: nums = [1, 3, -6, 4, -3] ผลลัพธ์ 4 เลือก [1, -6, 4, -3]

ขั้นตอนการแก้ปัญหา

1. pos = 0, neg = 0 (ความยาว subsequence จบด้วยบวก/ลบ)
2. วนแต่ละ n ใน nums:
   • ถ้า n < 0: neg = pos + 1
   • มิฉะนั้น: pos = neg + 1
3. คืน max(pos, neg)

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

class Solution:
    def solve(self, nums):
        pos = neg = 0
        for n in nums:
            if n < 0:
                neg = pos + 1
            else:
                pos = neg + 1
        return max(pos, neg)

ob = Solution()
nums = [1, 3, -6, 4, -3]
print(ob.solve(nums))

อินพุต

[1, 3, -6, 4, -3]

เอาต์พุต

4