Chương trình tìm phần tử tối đa sau khi giảm và sắp xếp lại bằng Python

Giả sử chúng ta có một mảng được gọi là arr. Chúng ta phải thực hiện một số thao tác trên arr để nó thỏa mãn các điều kiện này -

• Phần tử đầu tiên trong arr phải là 1.

• Chênh lệch tuyệt đối giữa bất kỳ 2 phần tử liền kề nào không được tối đa bằng 1.

Và có hai hoạt động. Chúng tôi có thể thực hiện hai loại hoạt động này bất kỳ lúc nào -

• Giảm bất kỳ giá trị nào của arr xuống một số dương nhỏ hơn.

• Sắp xếp lại các phần tử của arr theo thứ tự bất kỳ.

Chúng ta phải tìm giá trị lớn nhất có thể trong arr sau khi thực hiện các phép toán để thỏa mãn các điều kiện đã cho.

Vì vậy, nếu đầu vào là arr =[3,3,2,3,2], thì đầu ra sẽ là 3 vì, chúng ta có thể giảm phần tử cuối cùng xuống 1, sau đó sắp xếp lại chúng như [1,2,3,3 , 3], và tối đa là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sắp xếp danh sách arr

• arr [0]:=1

• đối với tôi trong phạm vi từ 1 đến kích thước của arr - 1, thực hiện

  • arr [i]:=tối thiểu là (arr [i - 1] + 1) và arr [i]

• trả về tối đa arr

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[3,3,2,3,2]

Đầu ra

3