C++ में उपसरणी उलटकर सरणी मान को अधिकतम करना

मान लीजिए हमारे पास nums नामक एक पूर्णांक सरणी है। इस सरणी का मान सभी i के लिए 0 से n-1 की सीमा में |nums[i]-nums[i+1]| के योग के रूप में परिभाषित है। जहां n सरणी का आकार है। हम दी गई सरणी के किसी भी उपसरणी का चयन कर सकते हैं और उसे उलट सकते हैं। हम यह ऑपरेशन केवल एक बार कर सकते हैं। फिर हमें अंतिम सरणी का अधिकतम संभव मान ज्ञात करना है।

यदि इनपुट [1,5,4,2,3] है, तो आउटपुट 10 होगा।

हल करने के चरण

ret := 0, extra := 0
n := nums का आकार
minVal := INF, maxVal := -INF
0 से n-2 तक के लिए: a := nums[i], b := nums[i+1], ret += |b-a|, extra = max(extra, |nums[0]-b| - |a-b|), extra = max(extra, |nums[n-1]-a| - |a-b|), maxVal = max(maxVal, min(a,b)), minVal = min(minVal, max(a,b))
ret + max(extra, (maxVal - minVal) * 2) लौटाएं

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int maxValueAfterReverse(vector<int>& nums) { 
        int ret = 0; 
        int extra = 0; 
        int n = nums.size(); 
        int minVal = INT_MAX; 
        int maxVal = INT_MIN; 
        for(int i = 0; i < n - 1; i++) { 
            int a = nums[i]; 
            int b = nums[i + 1]; 
            ret += abs(b - a); 
            extra = max(extra, abs(nums[0] - b) - abs(a - b)); 
            extra = max(extra, abs(nums[n - 1] - a) - abs(a - b)); 
            maxVal = max(maxVal, min(a, b)); 
            minVal = min(minVal, max(a, b)); 
        } 
        return ret + max(extra, (maxVal - minVal) * 2); 
    } 
}; 

int main() { 
    Solution ob; 
    vector<int> v = {1,5,4,2,3}; 
    cout << (ob.maxValueAfterReverse(v)); 
    return 0; 
}

इनपुट

{1,5,4,2,3}