โปรแกรมหา Element สูงสุดหลังลดค่าและเรียงใหม่ใน Python

ปัญหา

อาร์เรย์ arr Operations: 1) ลดค่า Element ใดๆ ให้เล็กลง (Positive) 2) เรียงใหม่ได้ทุกอย่าง เงื่อนไข: arr[0]=1, |arr[i]-arr[i-1]| ≤ 1 หา Max Value ที่เป็นไปได้

ตัวอย่าง

arr = [3,3,2,3,2] → Output: 3

ลดตัวสุดท้ายเป็น 1 → [3,3,2,3,1] → เรียง: [1,2,3,3,3] Max = 3

อัลกอริทึม (Greedy Sort + Cap)

1. Sort Array
2. Force arr[0] = 1
3. For i=1..n-1: arr[i] = min(arr[i], arr[i-1] + 1)
4. Return max(arr)

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

def solve(arr):
    arr.sort()
    arr[0] = 1
    for i in range(1, len(arr)):
        arr[i] = min(arr[i - 1] + 1, arr[i])
    return max(arr)

arr = [3,3,2,3,2]
print(solve(arr))  # 3

ความซับซ้อน

• Time: O(n log n) จาก Sort
• Space: O(1) In-place

เหตุผล: หลัง Sort แล้ว ค่าที่ i สูงสุดที่เป็นไปได้คือ arr[i-1]+1 (ความต่าง ≤ 1) ถ้าค่าเดิมมากกว่า ต้องลดลง