C++ এ অ্যারের মান সর্বাধিক করতে বিপরীত সাবারে

ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে আছে যাকে nums বলা হয়। এই অ্যারের মান |সংখ্যা[i]-সংখ্যা[i+1]| এর সমষ্টি হিসাবে সংজ্ঞায়িত করা হয়েছে। 0 থেকে n - 1 রেঞ্জের সকলের জন্য। যেখানে n হল অ্যারের আকার। আমরা প্রদত্ত অ্যারের যেকোনো সাবয়ারে নির্বাচন করতে পারি এবং এটিকে বিপরীত করতে পারি। আমরা শুধুমাত্র একবার এই অপারেশন করতে পারেন. তারপর আমাদের চূড়ান্ত অ্যারের সর্বোচ্চ সম্ভাব্য মান খুঁজে বের করতে হবে।

সুতরাং, ইনপুট যদি [1,5,4,2,3] এর মত হয়, তাহলে আউটপুট হবে 10।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

ret :=0, অতিরিক্ত :=0
n :=সংখ্যার আকার
minVal :=inf, maxVal :=-inf
আরম্ভ করার জন্য i :=0, যখন i
- a :=সংখ্যা[i], b :=সংখ্যা[i + 1]
- ret :=ret + |b - a|
- অতিরিক্ত :=সর্বাধিক অতিরিক্ত এবং |(সংখ্যা[0] - বি) - |a - b||
- অতিরিক্ত :=সর্বাধিক অতিরিক্ত এবং |(সংখ্যা[n - 1] - a) - |a - b||
- maxVal :=সর্বোচ্চ maxVal এবং সর্বনিম্ন a এবং b
- minVal :=সর্বনিম্ন minVal এবং সর্বোচ্চ a এবং b
রিটার্ন ret + সর্বাধিক অতিরিক্ত এবং (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);
   }
};
main(){
   Solution ob;
   vector<int> v = {1,5,4,2,3};
   cout << (ob.maxValueAfterReverse(v));
}

ইনপুট

{1,5,4,2,3}