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

โจทย์: กำหนดรายการตัวเลข nums หาความยาวสูงสุดของสับลิสต์ (Contiguous Sublist) ที่เพิ่มขึ้นอย่างเคร่งครัด (Strictly Increasing) โดยอนุญาตให้ลบองค์ประกอบได้สูงสุด 1 ตัว

ตัวอย่าง

Input: nums = [35, 5, 6, 7, 8, 9, 12, 11, 26]
Output: 7
เหตุผล: ลบ 12 ได้ [5, 6, 7, 8, 9, 11, 26] ยาว 7 ตัว เพิ่มขึ้นเคร่งครัด

อัลกอริทึม: Prefix/Suffix Length + Combine

คำนวณความยาวสับลิสต์เพิ่มขึ้นที่ลงท้ายที่แต่ละตำแหน่ง (end) และเริ่มต้นที่แต่ละตำแหน่ง (start) แล้วลองเชื่อมต่อโดยข้าม 1 ตัว

ขั้นตอนการทำงาน

1. end[i]: ความยาวสับลิสต์เพิ่มขึ้นที่ลงท้ายที่ index i
2. start[i]: ความยาวสับลิสต์เพิ่มขึ้นที่เริ่มต้นที่ index i
3. คำตอบเบื้องต้น = max(end, start) (กรณีไม่ลบอะไร)
4. ลองข้ามแต่ละ k: หาก nums[k-1] < nums[k+1] ให้เชื่อม end[k-1] + start[k+1]

โค้ด Python

def solve(nums):
    if not nums:
        return 0
    
    n = len(nums)
    end = [1] * n    # ความยาวสับลิสต์เพิ่มขึ้นลงท้ายที่ i
    start = [1] * n  # ความยาวสับลิสต์เพิ่มขึ้นเริ่มต้นที่ i
    
    # คำนวณ end: ซ้ายไปขวา
    for i in range(1, n):
        if nums[i] > nums[i - 1]:
            end[i] = end[i - 1] + 1
    
    # คำนวณ start: ขวาไปซ้าย
    for j in range(n - 2, -1, -1):
        if nums[j + 1] > nums[j]:
            start[j] = start[j + 1] + 1
    
    # กรณีไม่ลบอะไร
    res = max(max(end), max(start))
    
    # ลองลบแต่ละตัว k (1 ถึง n-2)
    for k in range(1, n - 1):
        if nums[k - 1] < nums[k + 1]:
            res = max(res, end[k - 1] + start[k + 1])
    
    return res

# ทดสอบ
nums = [35, 5, 6, 7, 8, 9, 12, 11, 26]
print(solve(nums))  # Output: 7

การทำงานทีละขั้นตอน (Trace)

nums = [35, 5, 6, 7, 8, 9, 12, 11, 26]

ลองลบ k=6 (ค่า 12): nums[5]=9 < nums[7]=11 ✓ → end[5]+start[7] = 5+2 = 7

ความซับซ้อน

• Time Complexity: O(n) - ผ่านอาร์เรย์ 3 รอบ
• Space Complexity: O(n) - สำหรับอาร์เรย์ end และ start

กรณีขอบ (Edge Cases)

print(solve([1, 2, 3, 4]))      # 4 (ไม่ต้องลบ)
print(solve([4, 3, 2, 1]))      # 2 (ลบ 1 ตัวได้สูงสุด 2)
print(solve([1, 3, 2, 4]))      # 3 (ลบ 3 ได้ [1,2,4] หรือลบ 2 ได้ [1,3,4])
print(solve([1]))               # 1
print(solve([]))                # 0