โปรแกรมหาผลรวมคู่ที่เล็กที่สุดโดยที่ระยะทางไม่ต่อเนื่องกันใน Python

สมมติว่าเรามีรายการหมายเลขที่เรียก ตอนนี้ให้เราพิจารณาคู่ของดัชนี (i, j) โดยที่ i 1. จากนั้นให้หาผลรวมของคู่ที่น้อยที่สุด

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[3, 4, 2, 2, 4] ผลลัพธ์จะเป็น 5 เราสามารถเลือกค่า 3 และ 2 ได้ ดังนั้นผลรวมทั้งหมดคือ 5 เราไม่สามารถเลือก 2 และ 2 ได้เนื่องจากพวกมัน อยู่ติดกันและละเมิดข้อจำกัด j - i> 1

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

• n :=ขนาดของ nums
• min_seen :=nums[0]
• ตอบ :=inf
• สำหรับฉันในช่วง 2 ถึง n - 1 ทำ
  • ans :=ขั้นต่ำของ ans และ (min_seen + nums[i])
  • min_seen :=ขั้นต่ำของ min_seen และ nums[i - 1]
• คืนสินค้า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(nums):
   n = len(nums)
   min_seen = nums[0]

   ans = float("inf")

   for i in range(2, n):
      ans = min(ans, min_seen + nums[i])

      min_seen = min(min_seen, nums[i - 1])
   return ans

nums = [3, 4, 2, 2, 4]
print(solve(nums))

อินพุต

[3, 4, 2, 2, 4]

ผลลัพธ์

5