पायथन में दो संख्या सूचियों से सबसे बड़ी दूरी वाली जोड़ी खोजने का प्रोग्राम

मान लीजिए हमारे पास A और B नामक दो संख्याओं की सूचियां हैं, और उनकी लंबाई समान है। हमें सभी 0 <= i < j < n के लिए अधिकतम मान ढूंढना है: |a[i]-a[j]| + |b[i]-b[j]| + |i-j|।

उदाहरण के लिए, यदि इनपुट A = [2, 4, 10, 6] और B = [3, 4, 7, 5] है, तो आउटपुट 14 होगा, जब i=0, j=2 पर |2-10| + |3-7| + |0-2| = 8+4+2=14 मिलता है।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (निरपेक्ष मान हटाकर 4 केस):

• ans := 0, n := len(a)
• प्रत्येक जोड़ी (s, t) के लिए [(-1,-1), (-1,1), (1,-1), (1,1)] में:
  • cur_min := inf, cur_max := -inf
  • i को 0 से n तक:
    • tmp := s*a[i] + t*b[i] + i
    • cur_min = min(cur_min, tmp)
    • cur_max = max(cur_max, tmp)
  • ans = max(ans, cur_max - cur_min)
• ans लौटाएं

उदाहरण कोड

class Solution:
    def solve(self, a, b):
        ans = 0
        n = len(a)
        for s, t in [(-1,-1), (-1,1), (1,-1), (1,1)]:
            cur_min = float("inf")
            cur_max = float("-inf")
            for i in range(n):
                tmp = s*a[i] + t*b[i] + i
                cur_min = min(cur_min, tmp)
                cur_max = max(cur_max, tmp)
            ans = max(ans, cur_max - cur_min)
        return ans

ob = Solution()
A = [2, 4, 10, 6]
B = [3, 4, 7, 5]
print(ob.solve(A, B))

इनपुट

[2, 4, 10, 6], [3, 4, 7, 5]

आउटपुट

14