मान लीजिए हमारे पास nums नामक संख्याओं की एक लिस्ट है और एक मान k है, हमें दी गई लिस्ट के आकार k की तीन नॉन-ओवरलैपिंग सबलिस्ट का सबसे बड़ा योग ढूंढना है।
उदाहरण के लिए, यदि इनपुट nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3], k = 3 है, तो आउटपुट 27 होगा, क्योंकि हम सबलिस्ट [2, 2, 2], [4, 4, 4], और [3, 3, 3] चुन सकते हैं, कुल योग 27 है।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम प्रीफिक्स सम और स्लाइडिंग विंडो का उपयोग करेंगे:
- P := [0] (प्रीफिक्स सम सरणी)
- A में प्रत्येक x के लिए, P[-1] + x को P के अंत में जोड़ें
- Q := [P[i + K] - P[i] for i in range(0, len(P) - K)] (आकार K की सभी सबलिस्ट के योग)
- prefix := Q की कॉपी, suffix := Q की कॉपी
- i को 0 से Q के आकार - 2 तक लूप चलाएं:
- prefix[i + 1] := max(prefix[i + 1], prefix[i])
- suffix[~(i + 1)] := max(suffix[~(i + 1)], suffix[~i])
- ret = max(Q[i] + prefix[i - K] + suffix[i + K] for i in range(K, len(Q) - K))
- ret लौटाएं
पायथन कार्यान्वयन
class Solution:
def solve(self, A, K):
P = [0]
for x in A:
P.append(P[-1] + x)
Q = [P[i + K] - P[i] for i in range(len(P) - K)]
prefix = Q[:]
suffix = Q[:]
for i in range(len(Q) - 1):
prefix[i + 1] = max(prefix[i + 1], prefix[i])
suffix[~(i + 1)] = max(suffix[~(i + 1)], suffix[~i])
return max(Q[i] + prefix[i - K] + suffix[i + K] for i in range(K, len(Q) - K))
ob = Solution()
nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3]
k = 3
print(ob.solve(nums, k))इनपुट
[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3], 3
आउटपुट
27
