C++-এ একবার রিভার্সালের পর সর্বোচ্চ এডজেসেন্ট অ্যাবসোলিউট ভ্যালু সম বের করা

মান লইয়া আমাদের একটি নাম্বার লিস্ট আছে 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

এটি সমাধান করতে, আমরা এই ধাপগুলো ফলো করব:

• যদি nums-এর সাইজ <= 1 হয়, 0 রিটার্ন করুন
• ans := 0
• n := nums-এর সাইজ
• i = 1 থেকে n-১ পর্যন্ত: ans += |nums[i] - nums[i-1]|
• orig := ans
• i = 1 থেকে n-2 পর্যন্ত:
  • ans = max(ans, orig - |nums[i] - nums[i+1]| + |nums[0] - nums[i+1]|)
  • ans = max(ans, orig - |nums[i] - nums[i-1]| + |nums[n-1] - nums[i-1]|)
• pp, pm, mp, mm ইনিশিয়ালাইজ করুন -|nums[1] - nums[0]| এর সাথে উপযুক্ত চিহ্ন দিয়ে
• j = 2 থেকে n-2 পর্যন্ত:
  • jerror := |nums[j+1] - nums[j]|
  • ans আপডেট করুন pp, pm, mp, mm ব্যবহার করে
  • pp, pm, mp, mm আপডেট করুন
• ans রিটার্ন করুন

বेहतर বোঝার জন্য ইমপ্লিমেন্টেশন দেখুন:

উদাহরণ

#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);
}

ইনপুট

{2, 4, 6}

আউটপুট

6