मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और दो मान x और y हैं, हमें nums में दो नॉन-ओवरलैपिंग सबलिस्ट्स का अधिकतम योग ढूंढना है जिनकी लंबाई क्रमशः x और y है।
उदाहरण के लिए, यदि इनपुट nums = [3, 2, 10, -2, 7, 6], x = 3, y = 1 है, तो आउटपुट 22 होगा, क्योंकि लंबाई 3 के लिए हम [3, 2, 10] चुनते हैं और लंबाई 1 के लिए [7]।
समाधान दृष्टिकोण
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
P := [0]से शुरू करें- प्रत्येक
xके लिएAमें:P.append(P[-1] + x)(प्रीफिक्स सम) - एक फंक्शन
solve(len1, len2)परिभाषित करें:Q := [P[i+len1] - P[i] for i in range(len(P)-len1)]prefix := Qकी कॉपीiके लिए 0 सेlen(prefix)-1:prefix[i+1] = max(prefix[i+1], prefix[i])ans := -infinityiके लिएlen1सेlen(P)-len2तक:left := prefix[i-len1]right := P[i+len2] - P[i]ans := max(ans, left+right)
ansलौटाएं
- मुख्य मेथड से:
max(solve(len1, len2), solve(len2, len1))लौटाएं
उदाहरण कोड
class Solution:
def solve(self, A, len1, len2):
P = [0]
for x in A:
P.append(P[-1] + x)
def solve(len1, len2):
Q = [P[i+len1] - P[i] for i in range(len(P)-len1)]
prefix = Q[:]
for i in range(len(prefix)-1):
prefix[i+1] = max(prefix[i+1], prefix[i])
ans = float("-inf")
for i in range(len1, len(P)-len2):
left = prefix[i-len1]
right = P[i+len2] - P[i]
ans = max(ans, left+right)
return ans
return max(solve(len1, len2), solve(len2, len1))
ob = Solution()
nums = [3, 2, 10, -2, 7, 6]
x = 3
y = 1
print(ob.solve(nums, x, y))इनपुट
[3, 2, 10, -2, 7, 6], 3, 1
आउटपुट
22