परिचय
मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है और हम सूची में किसी भी सबलिस्ट को अधिकतम एक बार रिवर्स कर सकते हैं। इस ऑपरेशन को करने के बाद, हमें निम्नलिखित का अधिकतम संभव मान ढूंढना है:
$\displaystyle\sum\limits_{i=0}^{n-2}| nums[i+1] - nums[i] |$
तो, यदि इनपुट nums = [2, 4, 6] है, तो आउटपुट 6 होगा, क्योंकि जब हम [4, 6] को रिवर्स करते हैं तो हमें सूची [2, 6, 4] मिलती है और मान |2 - 6| + |6 - 4| = 6 होता है।
समाधान दृष्टिकोण
यह एक उन्नत एल्गोरिदमिक समस्या है जिसमें हम प्रीफिक्स/सफिक्स अंतरों और चार स्थितियों (++, +-, -+, --) को ट्रैक करके इष्टतम रिवर्सल ढूंढते हैं।
उदाहरण कोड
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& nums) {
if (nums.size() <= 1) return 0;
int ans = 0;
int n = nums.size();
for (int i = 1; i < n; i++) {
ans += abs(nums[i] - nums[i - 1]);
}
int orig = ans;
for (int i = 1; i < n - 1; i++) {
ans = max(ans, orig - abs(nums[i] - nums[i + 1]) + abs(nums[0] - nums[i + 1]));
ans = max(ans, orig - abs(nums[i] - nums[i - 1]) + abs(nums[n - 1] - nums[i - 1]));
}
int pp = -abs(nums[1] - nums[0]) + nums[0] + nums[1];
int pm = -abs(nums[1] - nums[0]) + nums[0] - nums[1];
int mp = -abs(nums[1] - nums[0]) - nums[0] + nums[1];
int mm = -abs(nums[1] - nums[0]) - nums[0] - nums[1];
for (int j = 2; j < n - 1; j++) {
int jerror = abs(nums[j + 1] - nums[j]);
ans = max(ans, orig + pp - jerror - nums[j] - nums[j + 1]);
ans = max(ans, orig + pm - jerror - nums[j] + nums[j + 1]);
ans = max(ans, orig + mp - jerror + nums[j] - nums[j + 1]);
ans = max(ans, orig + mm - jerror + nums[j] + nums[j + 1]);
pp = max(pp, -abs(nums[j] - nums[j - 1]) + nums[j - 1] + nums[j]);
pm = max(pm, -abs(nums[j] - nums[j - 1]) + nums[j - 1] - nums[j]);
mp = max(mp, -abs(nums[j] - nums[j - 1]) - nums[j - 1] + nums[j]);
mm = max(mm, -abs(nums[j] - nums[j - 1]) - nums[j - 1] - nums[j]);
}
return ans;
}
int main(){
vector<int> v = {2, 4, 6};
cout << solve(v);
return 0;
}
इनपुट
{2, 4, 6}
आउटपुट
6
निष्कर्ष
यह O(n) एल्गोरिदम सभी संभावित रिवर्सल पर विचार करके अधिकतम आसन्न अंतर योग की गणना करता है। चार स्टेट वेरिएबल्स (pp, pm, mp, mm) चिह्न संयोजनों को ट्रैक करते हैं। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।
