โปรแกรมนับ sublist ที่มีทั้ง max และ min หลังลบ 1 ตัวใน Python

คำอธิบายโจทย์

ให้ nums ลบได้สูงสุด 1 ตัว หาจำนวน sublist สูงสุดที่มีทั้งค่า max และ min ของ list ที่เหลือ

ตัวอย่าง

nums = [3, 2, 6, 2, 4, 10] → 8 (ลบ 10 ได้ [3,2,6,2,4] มี 8 sublists มีทั้ง max=6 และ min=2)

วิธีแก้ปัญหา

1. ฟังก์ชัน check(lst): นับ subarray ที่มีทั้ง min และ max
2. ติดตามตำแหน่งล่าสุดของ min และ max (min_pos, max_pos)
3. ที่แต่ละ i: เพิ่ม min(min_pos, max_pos) + 1 (จำนวน subarray จบที่ i ที่มีทั้งคู่)
4. ลองไม่ลบ, ลบ min (ถ้ามี 1 ตัว), ลบ max (ถ้ามี 1 ตัว) หาค่าสูงสุด

โค้ด Python

class Solution:
    def solve(self, nums):
        if len(nums) <= 1:
            return len(nums)
        
        def check(lst):
            mn, mx = min(lst), max(lst)
            min_pos, max_pos = None, None
            ret = 0
            for i, num in enumerate(lst):
                if num == mn:
                    min_pos = i
                if num == mx:
                    max_pos = i
                if min_pos is None or max_pos is None:
                    continue
                ret += min(min_pos, max_pos) + 1
            return ret
        
        ret = check(nums)
        for rem_cand in [min(nums), max(nums)]:
            if nums.count(rem_cand) == 1:
                idx = nums.index(rem_cand)
                ret = max(ret, check(nums[:idx] + nums[idx + 1:]))
        return ret

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

อินพุต

[3, 2, 6, 2, 4, 10]

เอาต์พุต

8