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

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า arr เราต้องดำเนินการบางอย่างกับ arr เพื่อให้เป็นไปตามเงื่อนไขเหล่านี้ -

• องค์ประกอบแรกใน arr ต้องเป็น 1

• ความแตกต่างที่แน่นอนระหว่าง 2 องค์ประกอบที่อยู่ติดกันต้องไม่เกิน 1

และมีการดำเนินการสองอย่าง เราสามารถดำเนินการสองประเภทนี้กี่ครั้งก็ได้ -

• ลดค่าของ arr ให้เป็นจำนวนบวกที่น้อยกว่า

• จัดเรียงองค์ประกอบของ arr ใหม่ให้อยู่ในลำดับใดก็ได้

เราต้องหาค่าสูงสุดที่เป็นไปได้ใน arr หลังจากดำเนินการเพื่อให้เป็นไปตามเงื่อนไขที่กำหนด

ดังนั้น หากอินพุตเป็นเหมือน arr =[3,3,2,3,2] ผลลัพธ์จะเป็น 3 เพราะเราสามารถลดองค์ประกอบสุดท้ายเป็น 1 ได้ แล้วจัดเรียงใหม่เช่น [1,2,3,3 ,3] และสูงสุดคือ 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เรียงลำดับรายการ arr

• arr[0] :=1

• สำหรับฉันในช่วง 1 ถึงขนาดของ arr - 1 ทำ

  • arr[i] :=ขั้นต่ำของ (arr[i - 1] + 1) และ arr[i]

• ผลตอบแทนสูงสุดของ 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,3,2,3,2]

ผลลัพธ์

3