ค่าสูงสุดของ |arr[i] - arr[j]| + |i

ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็ม n ตัว งานของเราคือสร้างโปรแกรมที่จะหาค่าสูงสุดของ |arr[i]-arr[j]| + |i-j|

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา:

อินพุต - array = {4, 1, 2}

เอาต์พุต - 4

คำอธิบาย -

|arr[0] - arr[1]|+|0-1| = |4-1| + |-1| = 3+1 = 4
|arr[0] - arr[2]|+|0-2| = |4-2| + |-2| = 2+2 = 4
|arr[1] - arr[2 ]|+|1-2| = |1-2| + |1-2| = 1+1 = 2

ในการแก้ปัญหานี้ วิธีง่ายๆ จะเป็นการใช้วิธี brute force ซึ่งจะใช้สองลูปและหาความต่างสูงสุด

แต่วิธีที่มีประสิทธิภาพจะเป็นการใช้คุณสมบัติของฟังก์ชันค่าสัมบูรณ์

ลองถอดรหัสสมการและหาวิธีแก้:

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

ตัวแรกและตัวที่สี่เหมือนกัน และตัวที่สองและตัวที่สี่เหมือนกัน ใช้สิ่งนี้เราจะสร้างสองอาร์เรย์ที่จะเก็บค่า arr[i]+- i

array1 จะเก็บค่า arr[i] + i

array2 จะเก็บค่า arr[i] - i

ดังนั้น เราจะหาค่าสูงสุดของสองค่าที่เป็น

max ((max(array1)-min(array1)), (max(array2)-min(array2)))

ตัวอย่างโค้ด

โปรแกรมแสดงการนำวิธีแก้ปัญหาของเราไปใช้,

#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

ค่าสูงสุดของ |arr[i] - arr[j]| + |i - j| ใน C++

ตัวอย่างโค้ด

ผลลัพธ์