โปรแกรมหาความยาวสับลิสต์เพิ่มแล้วลดมากสุดใน Python

สมมติว่ามีรายการตัวเลข nums ต้องการหาความยาวสับลิสต์ยาวสุด (ขั้นต่ำ 3) ที่เพิ่มขึ้นเคร่งครัดแล้วลดลงเคร่งครัด

ตัวอย่าง: nums = [8, 2, 4, 6, 3, 1] ผลลัพธ์ 5 สับลิสต์ [2, 4, 6, 3, 1]

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

1. i = 0, n = len(a), res = -inf
2. วนลูป بينما i < n-2:
   • st = i, linc = 0, ldec = 0
   • ขณะ i < n-1 และ a[i] < a[i+1]: linc++, i++
   • ขณะ i < n-1 และ a[i] > a[i+1]: ldec++, i++
   • ถ้า linc > 0 และ ldec > 0: res = max(res, i - st + 1)
   • ขณะ i < n-1 และ a[i] == a[i+1]: i++
3. คืน res if res >= 0 else 0

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

class Solution:
    def solve(self, a):
        i, n, res = 0, len(a), float("-inf")
        while i < n - 2:
            st = i
            linc, ldec = 0, 0
            while i < n - 1 and a[i] < a[i + 1]:
                linc += 1
                i += 1
            while i < n - 1 and a[i] > a[i + 1]:
                ldec += 1
                i += 1
            if linc > 0 and ldec > 0:
                res = max(res, i - st + 1)
            while i < n - 1 and a[i] == a[i + 1]:
                i += 1
        return res if res >= 0 else 0

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

อินพุต

[8, 2, 4, 6, 3, 1]

เอาต์พุต

5