मान लीजिए हमारे पास nums नामक एक ऐरे है जिसमें धनात्मक पूर्णांक हैं, हमें अधिकतम योग वाले तीन गैर-ओवरलैपिंग सबएरे ज्ञात करने हैं। यहां प्रत्येक सबएरे का आकार k होगा, और हम सभी 3*k प्रविष्टियों के योग को अधिकतम करना चाहते हैं।
हमें परिणाम को प्रत्येक अंतराल की प्रारंभिक स्थिति को दर्शाने वाले सूचकांकों की सूची के रूप में ज्ञात करना है। यदि कई उत्तर हैं, तो हम शब्दकोश क्रम में सबसे छोटा वाला वापस करेंगे।
तो यदि इनपुट [1,2,1,2,6,8,4,1] जैसा है और k = 2, तो परिणाम [0,3,5] होगा, तो सबएरे [1,2], [2,6], [8,4] हैं जो प्रारंभिक सूचकांक [0,3,5] से मेल खाते हैं।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -
- n := nums का आकार
- आकार 3 का एक ऐरे ret परिभाषित करें जिसे inf से भरें
- आकार n + 1 का एक ऐरे sum परिभाषित करें
- i := 0 से प्रारंभ करें, जब i < n, i बढ़ाते हुए, करें -
- sum[i + 1] = sum[i] + nums[i]
- आकार n का एक ऐरे posLeft परिभाषित करें
- आकार n का एक ऐरे posRight परिभाषित करें जिसे n - k से भरें
- i := k से प्रारंभ करें, currMax := sum[k] - sum[0], जब i < n, i बढ़ाते हुए, करें -
- newTotal := sum[i + 1] - sum[i + 1 - k]
- यदि newTotal > currMax, तो -
- currMax := newTotal
- posLeft[i] := i + 1 - k
- अन्यथा
- posLeft[i] := posLeft[i - 1]
- i := n - k - 1 से प्रारंभ करें, currMax := sum[n] - sum[n - k], जब i >= 0, i घटाते हुए, करें -
- newTotal := sum[i + k] - sum[i]
- यदि newTotal >= currMax, तो -
- currMax := newTotal
- posRight[i] := i
- अन्यथा
- posRight[i] := posRight[i + 1]
- req := 0
- i := k से प्रारंभ करें, जब i <= n - 2 * k, i बढ़ाते हुए, करें -
- l := posLeft[i - 1], r := posRight[i + k]
- temp := (sum[l + k] - sum[l]) + (sum[i + k] - sum[i]) + (sum[r + k] - sum[r])
- यदि temp > req, तो -
- ret[0] := l, ret[1] := i, ret[2] := r
- req := temp
- ret वापस करें
बेहतर समझ के लिए निम्न कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) { int n = nums.size(); vector <int> ret(3, INT_MAX); vector <int> sum(n + 1); for(int i = 0; i < n; i++){ sum[i + 1] = sum[i] + nums[i]; } vector <int> posLeft(n); vector <int> posRight(n, n - k); for(int i = k, currMax = sum[k] - sum[0]; i < n; i++){ int newTotal = sum[i + 1] - sum[i + 1- k]; if(newTotal > currMax){ currMax = newTotal; posLeft[i] = i + 1 - k; }else{ posLeft[i] = posLeft[i - 1]; } } for(int i = n - k - 1, currMax = sum[n] - sum[n - k]; i >=0 ; i--){ int newTotal = sum[i + k] - sum[i]; if(newTotal >= currMax){ currMax = newTotal; posRight[i] = i; }else{ posRight[i] = posRight[i + 1]; } } int req = 0; for(int i = k; i <= n - 2 * k; i++){ int l = posLeft[i - 1]; int r = posRight[i + k]; int temp = (sum[l + k] - sum[l]) + (sum[i + k] - sum[i]) + (sum[r + k] - sum[r]); if(temp > req){ ret[0] = l; ret[1] = i; ret[2] = r; req = temp; } } return ret; } }; main(){ Solution ob; vector<int> v = {1,2,1,2,6,8,4,1}; print_vector(ob.maxSumOfThreeSubarrays(v, 2)); }इनपुट
{1,2,1,2,6,8,4,1} 2आउटपुट
[0, 3, 5, ]