โปรแกรมหาความยาวสับลิสต์ติดต่อที่เพิ่มขึ้นอย่างเคร่งครัดหลังลบได้สูงสุดหนึ่งองค์ประกอบใน Python

สมมติว่ามีรายการตัวเลขชื่อ nums เราต้องหาความยาวสูงสุดของสับลิสต์ติดต่อที่เพิ่มขึ้นอย่างเคร่งครัดเมื่อเราสามารถลบองค์ประกอบได้สูงสุดหนึ่งตัวจากรายการ

เช่น ถ้าอินพุตคือ nums = [30, 11, 12, 13, 14, 15, 18, 17, 32] ผลลัพธ์จะเป็น 7 เนื่องจากลบ 18 ออกจะได้ [11, 12, 13, 14, 15, 17, 32] ซึ่งเป็นสับลิสต์ติดต่อเพิ่มขึ้นอย่างเคร่งครัดที่ยาวที่สุด ความยาว 7

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

• n := ขนาดของ nums
• pre := รายการขนาด n เติม 1
• for i ในช่วง 1 ถึง n-1 ถ้า nums[i] > nums[i-1] pre[i] := pre[i-1] + 1
• suff := รายการขนาด n เติม 1
• for i จาก n-2 ลงถึง 0 ถ้า nums[i] < nums[i+1] suff[i] := suff[i+1] + 1
• ans := max(max(pre), max(suff))
• for i ในช่วง 1 ถึง n-1 ถ้า nums[i-1] < nums[i+1] ans := max(ans, pre[i-1] + suff[i+1])
• คืนค่า ans

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

class Solution:
    def solve(self, nums):
        n = len(nums)
        pre = [1] * n
        for i in range(1, n - 1):
            if nums[i] > nums[i - 1]:
                pre[i] = pre[i - 1] + 1
        suff = [1] * n
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                suff[i] = suff[i + 1] + 1
        ans = max(max(pre), max(suff))
        for i in range(1, n - 1):
            if nums[i - 1] < nums[i + 1]:
                ans = max(ans, pre[i - 1] + suff[i + 1])
        return ans

ob = Solution()
nums = [30, 11, 12, 13, 14, 15, 18, 17, 32]
print(ob.solve(nums))

อินพุต

[30, 11, 12, 13, 14, 15, 18, 17, 32]

เอาต์พุต

7