Chương trình tìm phần tử lớn nhất sau giảm và sắp xếp lại trong Python

Cho mảng arr. Thực hiện phép toán: (1) Giảm bất kỳ phần tử nào thành số dương nhỏ hơn. (2) Sắp xếp lại thứ tự. Mục tiêu: arr[0] = 1, |arr[i] - arr[i-1]| ≤ 1. Tìm max(arr) có thể đạt được.

Ví dụ: arr = [3,3,2,3,2] → output = 3 (giảm 1 phần tử thành 1, sắp xếp [1,2,3,3,3]).

Giải thuật (Greedy sort + clamp)

• Sắp xếp arr tăng dần.
• arr[0] = 1.
• Duyệt i=1..n-1: arr[i] = min(arr[i-1] + 1, arr[i]).
• Trả về max(arr).

Code Python

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

Đầu vào / Đầu ra

Input: [3,3,2,3,2]
Output: 3