Python में एक समीकरण का अधिकतम मान खोजने का प्रोग्राम

मान लीजिए हमारे पास एक ऐरे points है जिसमें 2D प्लेन पर कोऑर्डिनेट पॉइंट्स हैं, वे x-मानों द्वारा सॉर्टेड हैं, जहां points[i] = (x_i, y_i) ताकि सभी 1 <= i < j <= points की संख्या के लिए x_i < x_j। हमारे पास एक और मान k है। हमें समीकरण y_i + y_j + |x_i - x_j| का अधिकतम मान ढूंढना है जहां |x_i - x_j| <= k और 1 <= i < j <= points की संख्या।

उदाहरण के लिए, यदि इनपुट है 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 है।

समाधान के चरण

left := 0, right := 1
max_value := -inf
while right < len(points):
- (xl, yl) := points[left]
- (xr, yr) := points[right]
- diff := |xr - xl|
- यदि left == right, तो right := right + 1
- अन्यथा जब diff <= k:
  - m := yl + yr + diff
  - max_value := max(max_value, m)
  - यदि yl >= yr - diff, तो right := right + 1
  - अन्यथा, left := left + 1
- अन्यथा, left := left + 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