โปรแกรมหาค่าสูงสุดของสมการใน Python

สมมติว่าเรามีอาร์เรย์ที่เรียกว่าจุดที่มีจุดพิกัดบนระนาบ 2 มิติ พวกมันจะถูกจัดเรียงตามค่า x โดยที่ points[i] =(x_i, y_i) ดังนั้น x_i

ดังนั้น ถ้าอินพุตเหมือนกับ points =[[2,4],[3,1],[6,11],[7,-9]] k =1 ผลลัพธ์จะเป็น 6 เพราะสองจุดแรก เป็นไปตามเงื่อนไข |xi - xj| <=1 ตอนนี้ถ้าเราคำนวณสมการเราจะได้ 4+ 1 + |2 - 3| =6 คะแนนที่สามและสี่ยังเป็นไปตามเงื่อนไขและส่งกลับค่า 11 + -9 + |6 - 7| =3 ดังนั้นสูงสุดคือ 6.

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

• ซ้าย :=0, ขวา :=1

• max_value :=-inf

• ในขณะที่ถูกต้อง <ขนาดของจุดทำ

  • (xl, yl) :=คะแนน[ซ้าย]

  • (xr, yr) :=คะแนน[ขวา]

  • diff :=|xr - xl|

  • ถ้าซ้ายเหมือนกับขวา แล้ว

    • ขวา :=ขวา + 1

  • มิฉะนั้นเมื่อ diff <=k แล้ว

    • m :=yl + yr + diff

    • max_value :=สูงสุดของ max_value และ m

    • ถ้า yl>=yr - diff แล้ว

      • ขวา :=ขวา + 1

    • มิฉะนั้น

      • ซ้าย :=ซ้าย + 1

    • มิฉะนั้น

      • ซ้าย :=ซ้าย + 1

• คืนค่า max_value

ตัวอย่าง

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

def solve(points, k):
   left, right = 0, 1
   max_value = float('-inf')

   while right < len(points):
      xl, yl = points[left]
      xr, yr = points[right]

      diff = abs(xr - xl)
      if left == right:
         right += 1
      elif diff <= k:
         m = yl + yr + diff
         max_value = max(max_value, m)
         if yl >= yr - diff:
            right += 1
         else:
            left += 1
      else:
         left += 1

   return max_value

points = [[2,4],[3,1],[6,11],[7,-9]]
k = 1
print(solve(points, k))

อินพุต

[[2,4],[3,1],[6,11],[7,-9]], 1

ผลลัพธ์

6