C++-এ |arr[i] - arr[j]| + |i - j| এর সর্বোচ্চ মান (Maximum Value of Expression)

এই সমস্যাতে, n সংখ্যক পূর্ণসংখ্যার একটি অ্যারে দেওয়া থাকে। আমাদের কাজ হল |arr[i] - arr[j]| + |i - j| এক্সপ্রেশনের সর্বোচ্চ মান বের করা।

উদাহরণ

ইনপুট: array = {4, 1, 2}

আউটপুট: 4

গাণিতিক বিশ্লেষণ

অবсолют ভ্যালুর বৈশিষ্ট্য ব্যবহার করে এক্সপ্রেশনকে দুটি 케이সে ভাগ করা যায়:

arr[i] - arr[j] + i - j = (arr[i] + i) - (arr[j] + j)
arr[i] - arr[j] - i + j = (arr[i] - i) - (arr[j] - j)

তাই দুটি অ্যারে তৈরি করুন:

• array1[i] = arr[i] + i
• array2[i] = arr[i] - i

উত্তর = max( max(array1) - min(array1), max(array2) - min(array2) )

C++ প্রোগ্রাম উদাহরণ (Brute Force)

#include <iostream>
using namespace std;

int maxDiff(int arr[], int n) {
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ans = max(ans, abs(arr[i] - arr[j]) + abs(i - j));
    return ans;
}

int main() {
    int array[] = {5, 7, 1, 2};
    int n = sizeof(array) / sizeof(array[0]);
    cout << "The maximum value of |arr[i] - arr[j]| + |i-j| is " << maxDiff(array, n);
    return 0;
}

আউটপুট

The maximum value of |arr[i] - arr[j]| + |i-j| is 7